E Talbot

R Lardé

F Gourbilleau

C Dufour

P Pareige

Si nanoparticles in SiO 2 : An atomic scale observation for optimization of optical devices

Keywords: 61.46.-w -Structure of nanoscale materials 68.37.-d -Microscopy of surfaces, interfaces, and thin films 81.15.Cd -Deposition by sputtering

Three-dimensional imaging of silicon nanoclusters array in silicon-rich silicon oxide layers was evidenced and studied. The atom probe tomography technique allows to give the composition of the nanoclusters and the composition of the interface with the silica matrix. These results give new insights for the understanding of the properties of Si-based photonic devices.

Introduction. -The development and optimization of Si-based photonic or memory devices [1][2][3][4][5], compatible with silicon integration technology, need to understand the precipitation of Si and the characteristic of Si nanoclusters (Si-nc) and the local chemical composition in Si/SiO 2 system. These Si-nc are deeply studied as sensitizer of erbium ions for silicon-based planar optical amplifier applications at 1.54 µm which is the wavelength used as standard in optical telecommunication [6][7][8][9]. A way to synthesize these nanoparticles consists in annealing at high temperature silicon-enriched silicon oxide (SRSO) leading to phase separation between Si and SiO 2 . The understanding, modelling and prediction of the optical properties of these materials require an accurate determination of the nanostructure of the system such as the phase composition, the nanoclusters size distribution and number density as well as roughness, thickness and composition of the Si/SiO 2 interface. The Si-nc/SiO 2 interface has been suspected to governs, to a large extent, the optical properties of Si-nc. The presence of a thin ∼1 nm substoichiometric silicon oxide interface has been reported as playing a critical role in the emission properties [10,11]. In addition, it has been demonstrated that very small Si-nc, even amorphous, still have an efficient sensitizing effect towards Er ions [9,12] and the relating energy transfer is highly dependent on the Si-nc-Er separating distance [13,14]. For these reasons, numerous studies focus (a) E-mail: etienne.talbot@univ-rouen.fr on Si/SiO 2 interface investigations because of the strong technological interest for the achievement of efficient optical and semiconductors devices.

In this letter, a new approach, using a femtosecond laserassisted wide-angle tomographic atom probe for studying Si-SiO 2 system is described. This technique allows to report the quantitative chemistry of Si-nanoparticles, their true size distribution and the nature of the Si/SiO 2 interface.

Experimental. -A set of SRSO/SiO 2 multilayers (MLs) were deposited on Si substrates ([100] oriented) by an alternative reactive magnetron sputtering of a pure silica target under a plasma of 50% H 2 + 50% Ar to obtain SRSO sublayers, owing to the ability of hydrogen to reduce oxygen [15], and under a plasma of pure Ar to deposit the SiO 2 sublayers. More detail of this reactive process can be found elsewhere [15]. The MLs were grown at 650 • C with a power density of 1.3 W cm -2 and were subsequently annealed at 900 • C for 1 h in a forming gas to favour the phase separation between Si and SiO 2 and achieve good photoluminescence properties. This annealing temperature corresponds to the best heating treatment for maximizing energy transfert between Si-nc and Er ions which is one of the key parameter for the achievment of net gain in Si-based optical amplifiers as reported in references [12,16]. The thicknesses of the SRSO and SiO 2 sublayers, determined by HRTEM, are 3.8 nm and 4 nm, respectively. Results and discussions. -Figure 1 shows a crosssectional HRTEM image of the SRSO/SiO 2 multilayers (carried out on a Topcon 002B on samples prepared in the cross-section configuration). The presence of crystalline Si-nanoparticles in the SRSO sublayers is revealed (as shown in the inset) when diffraction conditions are fulfilled. These particles are only localised, as expected, in SRSO layers. Therefore, even with this high resolution technique, it is difficult: i) to estimate the particle number density and ii) to characterize nanoprecipitate/matrix interfaces. Complementary information is provided by high resolution analysis technique such as laser-assisted three-dimensional atom probe tomography (3D-APT). It is able to provide a spatial chemical map at the atomic scale [17]. The basic principle of the technique is the field evaporation of surface atoms. During the analysis, a high positive DC voltage (several kilovolts) is applied on the sample in order to create an electric field at the apex of the tip. The superposition of femtosecond laser pulses lead to the controlled evaporation of the specimen. The evaporated ions are collected on a position-sensitive detector which measure the time of flight of individual ions (time of flight mass spectrometry) and the impact position of each ion on the surface of the detector. These data permit the three-dimensional reconstruction of the analyzed volume at the atomic scale. A more detailed description of the principles of the technique may be found in references [18][19][20][START_REF] Miller | Atom Probe Tomography: Analysis at the Atomic Level[END_REF]. The recent development of this technique allows to carry out analyses of "poor" conductor materials by using laser-assisted evaporation [START_REF] Gault | [END_REF]. In order to be a quasi-stereographic projection microscope and to locally increase the required electrical field and thus to perform 3D-APT experiments, the sample needs to be tip-shaped with a small cone angle and a radius of curvature of the extremity smaller than 50 nm. Such a requirement is achieved using an annular milling procedure with a focus ion beam (FIB) [23,24]. In order to prevent ion beam damages and gallium implantation, the samples were previously protected with a 300 nm Cr layer. The final steps of the process consist in the milling of the tips at a low acceleration voltage (2 kV). The laser-assisted wide-angle tomographic atom probe (LA-WATAP) used in this work is a CAMECA version. The experiments were performed at 80 K, using UV (343 nm) femtosecond laser pulses (50 nJ, 350 fs) with a pulse repetition rate of 100 kHz.

m n 1 5 x 3 1 x 3 1 : x o B 3 i S O s i s y l a n A n o i t c e r i d
Figure 2 shows a 3D reconstruction image of the SRSO/SiO 2 multilayers analysed by LA-WATAP. The stacking of the SRSO and SiO 2 sublayers in the growth/analysis directions is clearly visible. In the SRSO sublayers indicated by an arrow and dashed-line, a higher Si content is evidenced and in some parts, Si-nc can be detected. In order to visualize clearly the presence of the Si-nanoclusters, a 3D iso-concentration surfaces image, which map the Si-rich concentration zones, is performed and shown in fig. 3(a). This figure corresponds to the fig. 2 where areas with %Si > 75% are in red (i.e. Si-ncs) and areas with %Si = 33% (i.e. SiO 2 matrix) are in green. The expected distribution of Si-nc (in red) in SRSO sublayers between pure silica sublayers (in green) is evidenced. The corresponding concentration profile in at.% along the growth direction of the multilayer is presented in fig. 3(b). The abscise axis corresponds to both growth and analysis direction while the y-axis give the atomic concentration in at.% of Si or O atoms. The measured atomic composition evidences the alternating stacking sequence of deposited nano-layers with pure silica sublayers (X Si ≈ 34.3 ± 0.3 at.% and X O ≈ 65.7 ± 0.3 at.%) separated by Si-enriched regions (X Si ≈ 51.0 ± 0.3 at.% and X O ≈ 49.0 ± 0.3 at.%). Thus the Si excess (%Si excess = X Si (1 -1 2 XO XSi ) in the 3.8 nm thick SRSO sublayers is estimated to ∼26%. The Si-content in the SRSO sublayer is found to be X Si ≈ 41.9 ± 0.3% (and X O ≈ 58.1 ± 0.3%) which is significantly higher than a pure silica matrix (X Si = 33.3% and X O = 66.7%). This local measured composition allows to assess that only a fraction of 50% of the Then, the last region (R3) is the silica matrix X matrix Si ≈ 30 ± 3 at.%). The presence of 20 at.% O in the core of the Si-nanoclusters is surprising and in contradiction with some previous experimental results where the nanoclusters are given as pure Si [10,13,25]. It is well known that APT analysis of phases with large different field of evaporation as it is the case with Si-nc in pure SiO 2 , leads to a local magnification effect artefact [START_REF] Miller | Atom Probe Field Ion Microscopy[END_REF]. This latter, when the particle is a low-evaporation-field (E L ) phase embedded in a high-evaporation-field matrix (E H ), is responsible of trajectory aberration of the ions during field evaporation process. The signature of the effect is the characteristic ellipsoidal shape of the clusters after 3D reconstruction as observed in fig. 3(a) and the concomitant increase of the number density of atoms (number of atoms per unit volume) in the nanocluster. In the case of Si-nc in SiO 2 , the density is multiply by a factor 4. Thus, this effect affects the size of the particle in the x-and y-direction, i.e., perpendicular to the analysis direction. However, the depth extension of the particle (in the z-or analysis direction) is accurate up to the interatomic distance. This increase in the density is also due to the introduction of atoms from originally located at the interface into the particle. Thus, in our case, this leads to an overestimation of the O concentration in the Si cluster present in the SRSO sublayers. This well known artefact (already observed in FeCu system for example) has been fully described and quantified by Vurpillot et al. [START_REF] Vurpillot | [END_REF]. When the difference between the field of evaporation of two phases: ϵ = 20% (where 100 * E H /E L = ϵ + 1) a composition bias of ∼25% may be observed [START_REF] Vurpillot | [END_REF]. This demonstrates that specific cares are needed in the interpretation of atom probe data.

Starting from the hypothesis that Si-nc are Si pure, as mostly expected in the optical amplifier devices community, the stoichiometry of the surrounding shell of Si-nc, silicon oxide (SiO y ) with different values of y, has been tested in order to make a correction of the local magnification effect and determine the exact composition of the interface. The model is simply based on the assumption that the cluster has a spherical shape (as seen with HRTEM images). Based on calculation from Vurpillot et al. [START_REF] Vurpillot | [END_REF] and Blavette et al. [29], the silicon concentration of the nanocluster is given by

X Si (r) = r 3 nc ρ Si + τ (r nc -∆e) 3 -r 3 nc ρ SiO2 X shell Si r 3 nc ρ Si + τ [(r nc -∆e) 3 -r 3 nc ] ρ SiO2 , (1)
where r nc is the radius of the Si-nc, ∆e is the thickness of the shell around the Si-nc, τ is the fraction of atoms belonging to the interface or the surrounding shell and artificially introduced into the clusters by the field effect, ρ Si = 50 at./nm 3 and ρ SiO2 = 66 at./nm 3 are, respectively, the density of Si and SiO 2 , and X shell Si is the mean Si concentration of shell. Using this relation, the evolution of Si concentration in the Si cluster as a function of the cluster size is calculated and is reported in fig. 4(c) for τ = 30%. This value has been taken from Blavette et al. work in which experimental and model are fitting in the case of a difference of 20% in the field of evaporation of the two phases [29] which is the difference estimated in our case. In this case, only the shell thickness and mean Si concentration of the shell are tuneable parameters. The experimental concentrations deduced from the reconstructed volume have also been reported on the same graph. The good correlation between the modelling curve and the experimental data confirm the different field effect described below and the good estimate of artefact parameters. To go further in the determination of the local microstructure, three hypotheses have been tested to determine the chemical composition of the shell around the Si-nc i) a pure silica shell has been considered which corresponds to an abrupt interface between Si and SiO 2 , ii) a sub-stoichiometric silicon oxide shell (SiO y ) with two different values of the Si content X Si = 50% or 75%, iii) a silicon oxide shell with a Si gradient with X Si ranging from X Si = 100% (near the core of the cluster) down to X Si = 33.3% (near the silica matrix). Blavette et al. [29] have demonstrated that, in the case of ϵ = 20%, the adatoms (in the clusters) from the surrounding matrix or interface cannot come from more than a thickness of 0.25 nm. To determine the composition of the surrounding shell of the Si-nc, we have calculated, for the different hypotheses, the thickness of the shell (∆e) which is able to reproduce the observed Si cluster concentration of about X measured Si ∼ 80 at.%. The cluster radius was taken to r nc = 1.6 nm (according to the composition profile on fig. 4(a)) and to r nc = 2.0 nm, which corresponds to the maximum size of the Si-nc. The results are reported in table 1.

In these multilayers, the results of the modelling allows to eliminate the hypothesis of sub-stoichiometric oxide (hypothesis 2 with X shell Si = 75%) and the linear silicon oxide shell (hypothesis 3), for which shell thicknesses of ∆e = 1.6 nm and ∆e = 0.8 nm, respectively, were obtained, which is not physically acceptable with the field evaporation process. The case of SiO 2 or SiO y (with X shell Si = 50%) shells give a better agreement with the composition profile of the Si-nc (fig. 4(a) and(b)). Moreover, we can note that the large shell thickness obtained in the case of sub-stoichiometric oxide with X shell Si = 75% evidences the fact that rich-Si shell cannot explain the detected oxygen content in the Si-nc.

Finally an explanation and modelling of the composition profiles obtained through the Si-nc are coherent with the description of Si pure nanoclusters embedded in the silica matrix. The local magnification effect artificially introduces oxygen in the reconstructed particles and shows diffuse interfaces (substoichiometric compositions). The correction of this effect leads to the conclusion that Si-ncs are pure Si embedded in silica. Daldosso et al. [10] have recently demonstrated (using HR-EFTEM and modelling) that Si-nc could be surrounded by a stressed SiO 2 shell, giving rise to a different contrast in TEM images. This interpretation is coherent with our results although atom probe is not able to detect stress, specifically in the elastic domain.

At the end, an accurate size distribution (corrected from apparent diffuse interfaces) of the silicon clusters (sub-nanometric detection) can be deduced from the 3D-APT technique (fig. 4(d)). The size ranges from 0.5 to 4.5 nm. The mean diameter is 2.9 nm and the nanoclusters number density is estimated to 5.7 ± 1.0 × 10 18 Si-nc/cm 3 . Such result highlights the new capability of the 3D-APT to detect small Si-nc embedded in SiO 2 compared to other techniques (HRTEM, XRD, Raman spectroscopy, EFTEM. . . ).

In summary, Si nanoclusters array in SRSO/SiO 2 multilayers was investigated by 3D atom probe tomography. 3D-APT results show at the atomic scale the characteristics of the nanoclusters. In the fabrication condition reported here which are the conditions usually applied for the Er-doped SRSO layers, the phase separation is incomplete. This is evidenced with a Si-supersaturation in the SRSO layers and a large scale distribution size of the nanoclusters. More important, it is shown the existence of an abrupt interface between the Si-nc and the matrix. The results described here are of primary importance for the understanding of the optical properties of future Sibased device as well as for their modelling. Thus, next steps of this work will be to deeply analyze the effect of higher annealing temperature (1000 and 1100 • C) on the local microstructure of these multilayers before studying the rare-earth (Er 3+ , Nd 3+ )-doped SRSO layers. For this latter, such a powerful atomic scale technique will allow to give some correlation between the optical properties and the chemical surrounding of the rare-earth ions as well as the localization of these ions towards the Si nanocluster. This will lead to an optimization of the fabrication process and pave the way to the achievemen of net gain in such doped materials. * * *

Fig. 1 :

 1 Fig. 1: (Colour on-line) High-Resolution TEM image of the SRSO/SiO2 multilayers. Two crystallized Si-nanoclusters are revealed (white circles and magnified image (inset)).

Fig. 2 :

 2 Fig. 2: (Colour on-line) 3D reconstruction of the SRSO/SiO2 multilayers analysed by LA-WATAP. Each dot represents one atom (Si or O). The volume is 13 × 13 × 51 nm 3 . SRSO layers are indicated by arrows and dashed lines.

Fig. 3 :

 3 Fig. 3: (Colour on-line) (a) 3D iso-concentration of the SRSO/SiO2 multilayers (red: Si-nc). (b) Composition profile along the multilayer. initial silicon excess has precipitated in Si-nanoclusters. The 1 h-annealing time of the SRSO/SiO 2 multilayers and/or the annealing temperature fixed here at 900 • C are not long/high enough to ensure a complete phase separation of the system. This confirms the slow phase separation process at such a temperature as suggested by Iacona et al. [25], and confirmed by Wang et al. [26] who suggested continous phase separation process as function of annealing temperature. The Si-nc/SiO 2 interface has been analyzed by Daldosso et al. on composite Si-SiO 2 layers [10]. They concluded by means of XANES and EFTEM experiments on the presence of a diffuse interface of about 1 nm between Si-nc and the SiO 2 host matrix. Figure 4(a) and fig. 4(b) show nanoscale composition profiles across Si nanoclusters. The profile in fig. 4(a) evidences three regions: the first one (R1) is the core (∼3.2 nm) of the Si-nc where the Si concentration is constant and maximum (X core Si ≈ 80 ± 3 at.%). The R2 region is composed of a substoichiometric silicon oxide shell (SiO y ) where the Si concentration varies from X interface Si

Fig. 4 :

 4 Fig. 4: (Colour on-line) (a), (b) Composition profile across a Si particle in the analyse direction for a Si-nc. (c) Measured cluster concentration as function of cluster radius. (d) Size distribution of the Si-nc diameter in the SRSO layers.

Table 1 :

 1 Calculated apparent Si content (at.%) in a Si-nanoclusters with a radius of rnc = 1.6 nm and rnc = 2.0 nm, with τ = 30% and ∆e thickness.

		SiO 2		SiO X -X shell Si	= 50%	SiO X -X shell Si	= 75%	Linear SiO X
		∆e (nm)	X Si	∆e (nm)		X Si	∆e (nm)		X Si	∆e (nm)	X Si
	r nc = 1.6 nm	0.4	81.7%	0.6	80.6%	1.6	81.6%	0.8	81.7%
	r nc = 2.0 nm	0.5	81.7%	0.7	81.7%	2.0	81.6%	1.0	81.7%

This work was supported by the Upper Normandy Region and the French Ministry of Research in the framework of Research Networks of Upper-normandy. The authors would like to thank Dr F. Vurpillot for his technical help on 3D atom probe reconstruction.


Constant Colombo
email: constant.colombo@univ-lorraine.fr

Francis Lepage
email: francis.lepage@univ-lorraine.fr

René Kopp
email: rene.kopp@tdf.fr

Eric Gnaedinger
email: eric.gnaedinger@univ-lorraine.fr

Two SDN Multi-tree Approaches for Constrained Seamless Multicast

Keywords: Routing, Disjoint trees, QoE, Seamless, Multicast, Real-time stream, Delay Constrained, SDN

. Two algorithms are presented in this paper, which both fulfill the requirement of the architecture.

I. INTRODUCTION

In Content Delivery Networks (CDN), robustness is one of the main problematic, as it is directly responsible for network availability and thus service continuity.

TDF is a French network operator, mainly providing transport for real-time audio and video streams nationwide. Today, one of its most important activity is audiovisual transport, streaming most of DTT channels (Digital Terrestrial Television) and national radios from studios to broadcasting antennas all over the territory. TDF operates its own network which is independent from the Internet, but can be considered a CDN.

The carried traffic is a real-time stream. As a consequence, data cannot be re-transmitted in case of loss and must be transported as fast and as steady as possible. Any method associated with TCP cannot be used in this case. Also, any loss in the network may cause a multiplied impact in the content viewing, depending on the receiving equipment: Quality of Experience (QoE) [START_REF]Terms and definitions related to quality of service and network performance including dependability[END_REF] is one of TDF's main concern. As service continuity is a consequence of network availability, Quality of Service (QoS) [START_REF]Quality of experience requirements for IPTV services[END_REF] is to be considered for QoE issues to be solved: commitments on availability, latency, jitter, and Dest.

Fig. 1. Maximally independent delay constrained trees loss are specified for each business customer in the Service Level Agreement (SLA).

To ensure robustness in case of failure, traditional IP solutions rely on rerouting based on the Interior Gateway Protocol (IGP). TDF current solution is the standard Multicast VPN (MVPN) [START_REF] Rosen | RFC 6513 Multicast in MPLS/BGP IP VPNs[END_REF] over MPLS on a traditional IP network. MVPN is composed of two protocols IGMP and PIM that both relies on the IGP. Those protocols ensure the building of a multicast tree and its resiliency through rerouting. Such resiliency schemes necessarily imply micro-cuts of the service, and thus impact on the content viewing. End equipment are able to buffer and absorb a part of the rerouting time, which must be inferior to the buffer size plus the delay of the path. But end equipment's' buffers are very small due to the real-time constraint, and only rerouting performance can be improved, which is very costly.

Inspired from Seamless Protection Switching (SPS) [START_REF]ST 2022-7:2013 -SMPTE Standard -Seamless Protection Switching of SMPTE ST 2022 IP Datagrams[END_REF], we aim to propose a new architecture based on redundancy for reliable transport. SPS is a standard defining how two redundant streams should be combined into a single coherent stream, without any cut if any stream fails. Indeed, redundancy and specifically seamless switching can tend to the micro-cuts issue while assuring the continuity of service in case of failure.

The main idea of the proposed architecture is to build two maximally independent redundant trees from the source of the stream to the destinations as illustrated in Fig. 1.

Both of the trees are active and carry the data to the destination. Basically, the destination is capable of swapping seamlessly from one path stream to the other. This way, whenever a failure occurs, only one path is impacted per destination. There is no backup tree: both of them are active at the same time. The main drawback is the bandwidth utilization: carrying twice the data on disjoint trees means using much more network resources. As a consequence, one of the main goals is to minimize the total bandwidth utilization of the two trees.

As it is presented, the architecture is a proactive protection, implying offline computation of the trees. The complete robust scheme also ensure each tree robustness, accounting for multiple network failures.

Software Defined Networking (SDN) [START_REF] Denazis | RFC 7426 : Software-Defined Networking (SDN): Layers and Architecture Terminology[END_REF] is a new paradigm in which networks activities are separated in the control plane and the data plane. A controller handles decisions while network nodes only perform forwarding. This way, any functionality can be implemented seamlessly through controller programming, and various algorithms can be implemented in a centralized fashion. Fig. 2 illustrates the architecture of this paper's solution. The network is separated between three main planes : Control plane, responsible for decision elements, the Management plane, responsible for managing the network, and the Data plane which applies Control plane decisions and forwards traffic accordingly. An SDN controller usually contains Control and Management plane, while network nodes only support Data plane.

This paper is focused on the Path Computation Element (PCE) of the presented architecture. It is organized as follow: in Section II industrial constraints are described and transposed into a graph theory formulation. Section III reviews the related works on multicast reliability and the multi-tree computation problem. In Section IV, two algorithmic approaches are presented. Finally, both algorithms are experimentally evaluated in Section V.

II. MIDCMPT PROBLEM

A. Problem statement

Multicast is a method to send data to a group of receivers in a single transmission, rather than multiple transmissions. To perform multicast over a given network, the creation of a tree is needed. Network topology can be modelled as a graph, and tree computation is a well-known field of graph theory. In simple cases, Spanning Trees are usually easy to compute and efficient enough. TDF's constraint are the following: the data is a real-time continuous stream, and as such should be carried as fast as possible without loss. Also, network bandwidth should be managed: the network should be able to carry the streams and every other customer's traffic. The network is not dedicated to this single usage. As a consequence, minimising the total bandwidth usage is a major concern.

Links that do not have enough bandwidth for the stream are removed from the problem. Each edge of the graph receives a weight of 1: intuitively, saving network resources is equivalent to using as less links as possible. But this weighting scheme does not account for existing traffic nor network heterogeneity. A naive approach would be to use bandwidth consumption as weight, but given the heterogeneity of the network, it should be considered to prioritise some links : for example, a 10 Gb/s backbone link used at 10% should be less costly than a half full 1 Gb/s access link, even though the bandwidth consumption is greater.

As stated before, the real-time streaming constraint implies a constrained delay between the source and each destination. Each edge of the graph is set with the maximum link delay measured over a significant period. This ensures that over the real network, constraint is not violated.

At any time, any destination should be reached by two disjoint paths carrying the same stream, to ensure that in case of failure the stream reaches destination. This is called path diversity. More redundancy could be considered : if a destination si reached by more than two path, it is even less likely to be unreachable in case of link failure. But in the proposed architecture, all paths carry the stream, and thus consume bandwidth. Using more than two paths is too costly in network usage compared to the robustness gain.

Given the gathered data for the studied network, links are more likely to fail than nodes. Paths are then only required to be edge-disjoint. Node-disjointedness is stronger, because node-disjoint paths are inherently edge-disjoint. Nevertheless, the proposed algorithm can ensure node-disjointedness.

Given real network topologies, disjoint paths are not always possible. For geographic reasons, some areas may not be reachable by two distinct paths. This means a Single Point of Failure exists for such areas of the network, and cannot be bypassed. As a consequence, disjointedness is not required to be strict. The problem is then stated as finding Maximally Independent Delay Constrained Minimal Pair of Trees (MID-CMPT).

B. N P-hardness

The MIDCMPT problem is N P-hard and this section focuses on its proof. First, the Maximally Independent Delay Constrained Paths problem (MIDCP) is shown to be N P-hard by reduction to the Maximally Independent Paths problem (MIP). Then, MIDCP is generalised to MIDCMPT. Node and edge-disjointedness are similar from the problem formulation point of view.

The MIDCP problem can be formulated as follows : for a graph G 0 , find a pair of (s,t)-paths such as those path are maximally independent, delay constrained and lightest possible. An auxiliary graph G 1 is created by removing from G 0 all edges belonging only to (s,t)-paths violating the delay constraints. One can solve the MIDCP problem over G 0 by solving the MIP problem over G 1 . Since the MIP problem is known to be N P-hard [START_REF] Omran | Finding paths with minimum shared edges[END_REF], then by reduction the MIDCP is N P-hard.

MIDCP is a specific case of the MIDCMPT problem. Using the following MIDCMPT formulation, it appears that MIDCP is the N = 1 case : find a pair of trees from a source to N destinations such as those trees are maximally independent, delay constrained and lightest possible. By generalisation of MIDCP which is N P-hard, the MIDCMPT problem is N Phard.

III. RELATED WORKS

A. On Multicast reliability

Network survivability has been studied in [START_REF] Pirlot | IP/MPLS network modeling using Bayesian networks to improve double failure recovery[END_REF] within the same context, providing tools for modelling MVPN solutions and evaluating its reliability. It shows that even though improvement of the traditional architecture is possible, impact still exists.

In [START_REF] Ghannami | Efficient Fast Recovery Mechanism in Software-Defined Networks[END_REF], several paths are deployed proactively on network nodes, and activated quickly in case of failure, thanks to OpenFlow Fast Failover groups [START_REF] Mckeown | OpenFlow: Enabling Innovation in Campus Networks[END_REF]. This solution improves service availability. However, this scheme uses multiple paths, which is not as bandwidth-efficient as a multicast distribution.

[11] proposes a scheme based on multiple trees to ensure reliable multicast distribution in a datacenter. The main point is to avoid loss and enable rapid path rerouting. Constraints and goals may differ from our problem, but the approach is similar, though our proposed scheme uses simultaneously the two multicast trees.

A genetic algorithm is proposed in [START_REF] Kubler | Dual path communications over multiple spanning trees for networked control systems[END_REF] to deploy two spanning trees on Networked Controlled Systems to ensure communication reliability. The usage of a similar method will be considered in future works.

B. On MIDCMPT computation

To the best of our knowledge, no method has yet been proposed to compute MIDCMPT. To solve this problem, many heuristics have been proposed such as in [START_REF] Forsati | An efficient algorithm for bandwidth-delay constrained least cost multicast routing[END_REF], and even an exact solution in [START_REF] Feng | Delay constrained multicast routing: What can we learn from an exact approach?[END_REF].

[15] provides an algorithm to compute two trees in such a way that a node will always be reachable through one of the trees in an edge redundant network. It can account for costs and for a delay constraint. The first drawback of this work is that it is based on undirected graph, and cannot account for different costs on each direction. Given the industrial context of unidirectional transmission, network links are to be considered directed. The second drawback is that this algorithm works on an edge redundant graph, which means that, for any given pair of vertices, there exists at least two strictly independent paths between those vertices. In practice this is not the case.

[16], [START_REF] Bejerano | Efficient Construction of Directed Redundant Steiner Trees[END_REF], [START_REF] Bejerano | Link-coloring based scheme for multicast and unicast protection[END_REF] intended to provide a new algorithm, based on directed graphs and resulting in a close to optimal solution. This method does not account for delay constraint and works on graphs with specific properties. Author's previous work intended to propose a new version of this algorithm, delay constrained and graph agnostic. Adaptation of [START_REF] Bejerano | Optimal construction of redundant multicast trees in directed graphs[END_REF], [START_REF] Bejerano | Efficient Construction of Directed Redundant Steiner Trees[END_REF], [START_REF] Bejerano | Link-coloring based scheme for multicast and unicast protection[END_REF] was not trivial, had a high computational cost and results showed that the algorithm often did not provide valid solutions.

IV. PROPOSED ALGORITHMS

A. Red Tree First -RTF

The concept of this algorithm is quite simple: a first delay constrained tree is computed iteratively using a delay constrained shortest path algorithm. Then a second tree is computed accounting for the first tree.

1) Delay constrained shortest path algorithm: Two delay constrained shortest path algorithm are selected for this work : Lagrange Relaxation based Aggregated Cost (LARAC) [START_REF] Juttner | Lagrange relaxation based method for the QoS routing problem[END_REF] based on Dijkstra algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF] and Constrained Bellman-Ford algorithm (CBF) [START_REF] Widyono | The design and evaluation of routing algorithms for realtime channels[END_REF] based on Bellman-Ford algorithm [START_REF] Bellman | On a routing problem[END_REF].

The LARAC procedure can be described as follows : for a given delay constraint, Dijkstra algorithm is applied iteratively to reweighted versions of the graph until weight and delay conditions are met. The weighting depends on previously computed paths, weight and delay.

The CBF algorithm is a breadth-first search, discovering paths with increasing delay while recording the shortest path to each node visited, until the exploration delay exceeds the delay constraint.

2) RTF explanation: The Red Tree First (RTF) procedure consists in computing one tree first, then the second one. A tree is computed as follows : for each destination not yet reached, a delay constrained shortest path algorithm is applied from source. Only the lightest path found is added to the tree. Every edge of the graph belonging to the tree receives a null weight. Delay is not altered. This operation is repeated until all destinations are reached by this first tree. Once the tree complete, all edges of the graph belonging to the tree receive a maximal weight. This maximal weight is the total weight of the graph. The second tree is then calculated using the same process over the modified graph.

RTF can also aim for maximal node-disjointedness. Before the second tree computation, all incoming edges of nodes belonging to the first tree must receive the maximal weight.

This procedure tends to find lightest trees under delay constraint. Independence is not guaranteed, as the lightest path is not always part of the maximally independent pair of paths. Nevertheless, by weighting the edges of the first tree with the total weight of the graph, the procedure ensures that those links will be used as last resort to build the second tree. This is easily proven, as any other path is lighter than the complete graph.

This scheme ensures that two trees are found, fitting the delay constraint. Independence and cost are accounted for, but not a priority. The proposed RTF procedure is detailed in Algorithm 1, and illustrated in Fig. 3.

P min ← E 4:
for t ∈ T r do

T b ← T r -{t min } 12: A r ← A r ∪ P min 13:
for e ∈ P min do The second proposed algorithm is based on a multipath algorithm SHaring-Edges Restrained PAths (SHERPA) [START_REF] Colombo | Sherpa : a SDN Multipath Approach to Eliminate Resilience Impact on Video Streams[END_REF]. IS computes iteratively pairs of paths using SHERPA, and assigns them to the trees depending on the maximum independence affectation.

1) SHERPA:

This algorithm is to be published by the authors in [START_REF] Colombo | Sherpa : a SDN Multipath Approach to Eliminate Resilience Impact on Video Streams[END_REF], but this section describe the main idea. In a graph G = (V, E), for a given pair (s, t) ∈ V × V , the SHERPA algorithm finds two delay constrained maximally edge-disjoint paths from s to t. It is based on the Suurballe-Tarjan algorithm [START_REF] Suurballe | A quick method for finding shortest pairs of disjoint paths[END_REF], which does not account for delay constraint and ensures only strict disjointedness. In short, the alterations to this original algorithm are: the replacement of the shortest path algorithm by a delay constrained algorithm; a reweighting scheme instead of the deletion of some links to provide relaxed disjointedness.

Based on Suurballe-Tarjan algorithm variation for nodedisjointedness, SHERPA also propose a variation to find delay constrained maximally node-disjoint paths. This variation can be used in IS to find for node-disjoint trees.

2) IS explanation: The IS procedure iterates SHERPA algorithm instances as follows : for each destination not yet reached by the trees, SHERPA algorithm is applied from the source to find a pair of Maximally Independent Delay Constrained Lightests Paths. Each path is assigned to a tree, depending on which affectation provides maximal independence. When no decision can be made for a given destination (i.e. provided independence is equal for both affectations), it is skipped and treated later. If no decision can be made for any of the remaining destinations, one random affectation is made, and the process restarted for every other not reached destinations. This process is repeated until all destinations are reached. Note that the order in which destinations are treated does not matter on the final result. for t ∈ T do 13:

P 1 , P 2 ← SHERP A(s, t, ∆) 14: if |(A r ∪ P 1 ) ∩ (A b ∪ P 2 )| > |(A r ∪ P 2 ) ∩ (A b ∪ P 1 )| then 15: A r ← A r ∪ P 1 16: A b ← A b ∪ P 2 17: T ← T -{t} 18: else if |(A r ∪P 1 )∩(A b ∪P 2 )| < |(A r ∪P 2 )∩(A b ∪P 1 )| then 19: A r ← A r ∪ P 2 20: A b ← A b ∪ P 1 21: T ← T -{t} 22: end if 23:
end for 24: end while Node disjointedness can be achieved by using the nodedisjoint variation of SHERPA algorithm, and to check for common vertices instead of common edges for path assignation.

The proposed IS scheme ensures maximal path diversity for every destination. Path cost is minimized, but total tree cost is not guaranteed to be minimized, as path affectation only depends on path diversity. The complete procedure is detailed in Algorithm 2, and illustrated in Fig. 4.

C. Validity of the solutions

Nothing guarantees the absence of cycle or the uniqueness of path from source to a vertex in a tree. That is to say a solution provided by one of the algorithms is a pair of valid trees. The only guarantee at this point is that the delay constraint is respected on at least one of the paths for each destination.

To ensure the validity of the results, two steps are necessary : removing cycles, and selecting unique paths.

Cycles can be easily found through Depth First Search (DFS). When an already visited node is met by the DFS, this means the last edge belongs to a cycle, goes towards the source, and should be removed. The DFS is then restarted. A specific case is met when the cycle is between two nodes, with an edge in each direction. These 2-length cycles are first treated as any other cycle, but kept in memory. It has been observed in practica that such cases necessitates a specific treatment. After treating all cycles, a procedure must be applied to each 2-length cycle met to select which direction must be kept. Algorithm 3 details the procedure. Basically, either one direction is needed to keep the tree continuous, or the shortest delay path between the two nodes is kept, to ensure that the delay constraint is not violated. This scheme always works if a single 2-length cycle is met, but might fail when multiple 2-length cycle appear.

Algorithm 3 2-length cycles elimination procedure

Input: A directed graph G = (V, E) weighted with cost C
and delay D, a source s, a set of destinations T , a delay constraint ∆. A pseudo-tree A ∈ E without cycle. list B of 2-length cycles. Output: A pseudo-tree A without cycle.

1: P A (v) denotes the predecessors of v in set of edges A 2: for (x, y) ∈ B do 3:

A ← A \ (x, y), (y, x) 4:
if |P A (x)| = 0 then 5:

A ← A + ( y, x) 6:
else if |P A (x)| = 0 then 7: A ← A + (y, x)

A ← A + (x, y) 8:
A ← A + (x, y)

end if 19: end for Once cycles are removed, to ensure the validity of the results, unique path to destinations must be selected. For any vertex with more than two predecessor in a tree, the lightestdelay path from source is selected and only the matching predecessor is kept. All other unnecessary edges are removed. Algorithm 4 details the procedure.

In summary, to obtain a valid solution one must follow the process:

• DFS to find and break cycles while keeping in memory 2-length cycles met; • Treat 2-length cycles using Algorithm 3;

• Eliminate multiple paths using Algorithm 4.

Algorithm 4 Multiple path elimination procedure

Input: A directed graph G = (V, E) weighted with cost C and delay D, a source s, a set of destinations T , a delay constraint ∆. A pseudo-tree A ∈ E without cycle. Output: A valid tree A from s to every t ∈ T .

1: Function single path(v) 2: P A (v) denotes the predecessors of v in set of edges A 3: for p ∈ P A (v) do M is re-estimated 25: end while 26: Let L A ∈ V be the set of leaves of A 27: N ← L A \ T 28: while N = ∅ do 29:

for n ∈ N do 30:

Let E n ∈ E be the set of edges to vertexs n 31:

A ← A \ E n 32:
end for

33:

Let L A ∈ V be the new set of leaves of A 34:

N ← L A \ T 35: end while V. ALGORITHM EVALUATION

A. Experimentation Scheme

The two proposed algorithms are here evaluated in terms of performance and scalability.

1) Problem generation: Random graphs are generated given a number of nodes following an Erdõs-Rényi model. Three types of instances will be studied : small graphs n = 20, medium graphs n = 100 and TDF's network scale large graph n = 800.

Random links are added between connected component to ensure the connectivity of the whole graph. It could be argued that this is not the best model for networks. Statistical significance is discussed later.

The probability p of edge creation is chosen according to the expected number of edges. For small graphs, different degrees will be used. Sparse and dense graphs will be generated with p = 0.1 and 0.6 for n = 20. Medium graphs will be generated with p = 0.01 for n = 100. For large graph, around 1600 edges are wanted, which matches p = 0.002, to reflect a topology fo the same scale as TDF's network.

Edges are randomly assigned a class to reflect the heterogeneity of the topology, as stated in II. Each class matches an intervals for random delay and a weight.

One node is randomly selected as source and a set of different nodes as destinations. Around 10% of nodes are selected as destinations. Such random selection is not representative of a hierarchical network. On a Internet network, source and destinations are usually on the edge of the network while on an operator network such as the studied one, source is located on the network's core while the destinations are on the edge.

Network core is usually a highly connected part of the network while network's edge are less connected.

Using a heuristic such as the one proposed in [START_REF] Charikar | Greedy Approximation Algorithms for Finding Dense Components in a Graph[END_REF], it is possible to identify the "denser" region of the graph, that can be assimilated to the network's core. If the source is selected in this region while the destinations are selected outside of it, the problem is closer to the studied case. One could go even further and use classification or partition methods, but problem generation is not the core of this work.

To determine the delay constraint value, an assumption is made : the network is designed such as all nodes are reachable from source under delay constraint. Among the shortest-delay paths to every node, the one with the higher value still fits the delay constraint. It is a lower bound of the delay constraint, and it is chosen as constraint for the corresponding graph.

This way, a problem is guaranteed to have at least one solution, where the two trees are strictly identical and match the shortest-delay tree from source to each destination.

2) Indicators and significance: The observed performance indicators are :

• Computation time;

• Success : is a valid constrained tree found;

• Tree sharing: the proportion of shared edges of the smaller tree, as it will be the higher proportion; • Which algorithm gives a better result: this is estimated thanks to an objective function defined in equation ( 1). Let β denote the number of common edges between the trees. Objective function is defined by :

F(A r , A b ) = C(A r ) + C(A b ) + β * 2 i∈E C(i) (1)
It is easy to prove that this objective function aims for greater independence before lighter trees. All tree found by the algorithms match the delay constraint, that's why it does not appear in the function.

Experiments were led on a 2 core 4 Thread 2.9GHz CPU and 16 Go RAM machine, code implemented in Python 2.7.

B. Results

Table . I illustrates mean performance confidence interval at 99% probability for the tested characteristics over different instances sizes.

Over N problem instance, let X denote the tested performance indicator and X its mean. Tested population is random, of high size and its standard deviation is unknown. For an small sample 30 < n < 0.05 * N it comes that the 1 -α confidence interval is defined by :

x - L 2 ≤ X ≤ x + L 2 (2)
L 2 = t 1-α 2 ,n-1 * n i=0 (x i -x) 2 n(n -1) (3)
with x i , i ∈ [1; n] the sample values, x the sample mean and t 1-α 2 ,n-1 the Student variable. Confidence intervals of a proportion P of the population are defined by :

p - L 2 ≤ P ≤ p + L 2 (4)
L 2 = u 1-α 2 * p * (1 -p) n (5)
with p the sample proportion and u 1-α 2 the normal variable. Each instance type was generated and tested 1000 times.

C. Analysis

According to data, both of the algorithm perform well over small graphs. Few differences are observed, although IS is slightly better than RTF for a similar computation time. Overall, computation time and success rate are very satisfying.

On larger graphs, matching topologies of the same scale as TDF's network, significant differences can be observed.

First, the computation time is around fourty times higher for RTF than for IS. This is due to the fact that each iteration, RTF evaluates multiple possibilities, and its complexity grows faster than IS. On the other hand, RTF often gives better results than IS, for a similar tree independence. This means that the solution found is close to the same local optimum, but RTF often finds closer results. Finally, success rate drops significatively for both algorithms.

In any case, both algorithm provide a solution in reasonnable operationnal time. Note that when a solution is not found, it is because of the appearance of more than one 2length cycles in the process that is not yet well accounted for. A more complex solution could raise the success rate, while increasing the computation time.

D. Weaknesses of the evaluation

The main weakness of this experimental scheme is the network model itself. A first approach to improve the scheme is to make Erdõs-Rényi parameters vary to observe many network types, but this creates a large number of different tests types. Plus, as shown in [START_REF] Newman | Random graphs as models of networks[END_REF], random graphs are not an ideal way to evaluate algorithm as they may not be representative. As a consequence, it could be argued that our results are not completely representative of algorithm performance.

VI. CONCLUSION

In this paper we presented a new SDN architecture for Seamless Multicast distribution, which is based on redundant trees to ensure that a real-time stream is carried without interruption from a source to multiple destinations. We proposed two centralized algorithms called RTF and IS to compute maximally edge or node independent delay constrained trees and evaluated their performance. Both algorithms account for global bandwidth utilization. We showed that, though these algorithm do not guaranty an optimal solution, they meet the requirement of the multiple constraints within reasonable time. RTF complexity grows faster with higher instances, but it gives more optimal results in terms of bandwidth consumption.

The mentionned architecture must guaranty continuity of service in case of failure in order to be more efficient than traditional solutions in terms of QoE. This paper detailed the PCE element, and future works will aim to complete the architecture : trees resiliency, failure recovery behaviour, management plane elements...

Algorithm 1

 1 Red Tree First algorithm Input: A directed graph G = (V, E) weighted with cost C and delay D, a source s, a set of destinations T , a delay constraint ∆. Output: Two delay constrained maximally edge-disjoint lightest trees A r , A b from s to every t ∈ T . 1: T r ← T 2: while T r = ∅ do 3:

17 :T

 17 for e ∈ A r do 18: C(e) ← i∈E C(i) 19: end for 20: T b ← T 21: while T b = ∅ do 22: P min ← E 23: for t ∈ T b do 24: P t ← LARAC(s, t, ∆) 25:if C(P t ) ≤ C(P min ) then 26:P min ← P t b ← T b -{t min } 31: A b ← A b ∪ P min 32:for e ∈ P min do 33:

Fig. 3 .

 3 Fig. 3. RTF Illustration

Algorithm 2 7 :P 1 , P 2 ← 9 :

 27129 Iterative SHERPA algorithm Input: A directed graph G = (V, E) weighted with cost C and delay D, a source s, a set of destinations T , a delay constraint ∆. Output: Two delay constrained maximally edge-disjoint lightest trees A r , A b from s to every t ∈ T . 1: A r ← ∅ 2: A b ← ∅ 3: previous ← |T | 4: while T = ∅ do 5: if |T | = previous then 6: u ← rand(T ) SHERP A(s, u, ∆) 8: A r ← A r ∪ P 1 A b ← A b ∪ P 2

  Fig. 4. IS Illustration

else 9 : 13 :

 913 s x ← Shortest delay path from s to x 10: s y ← Shortest delay path from s to y 11: d x ← D(s y ) + D((y, x)) 12: d y ← D(s x ) + D((x, y)) if d x < d y then 14:

  end for 15: u ← min p∈P A (v) (d[p]) 16: for p ∈ P A (v) \ {u} do 17: A ← A \ {(p, v)} 18: end for 19: end Function 20: 21: Let M be the set of vertices with more than one predecessor in A 22: while M = ∅ do 23: single path(rand(M )) 24: