Hailong Yang

Pascal Boulet

Marie-Christine Record

A rapid method for analyzing the chemical bond from energy densities calculations at the bond critical point

Keywords: Chemical bond, electron density topological properties, DFT, QTAIM

The quantum theory atoms in molecules (QTAIM) method has been used in this paper to characterize various bonding interactions in molecules and solid compounds. By using DFT-PAW calculations, complete electron density Laplacian distributions have been obtained and related to energies densities calculated at the bond critical points. From the analysis of these results a simple and rapid method, based solely on local energies densities calculations, is proposed to diagnose the bonding state, the polarizability and the deformation of the charge distribution.

I. Introduction

X-ray diffraction, as a unique tool for obtaining the experimental charge density in crystals, can be helpful in the study of chemical bonding in solids [START_REF] Koritsanszky | Chemical applications of X-ray charge-density analysis[END_REF]. By analyzing the X-ray determined charge densities with the quantum theory of atoms in molecules (QTAIM), the interactions or bonding between atoms can be quantitatively interpreted in the real space [START_REF] Koritsanszky | Chemical applications of X-ray charge-density analysis[END_REF][START_REF] Bader | Atoms in molecules: a quantum theory[END_REF]. The information obtained by combining theory and experiment allows for a better description of the atomic interactions, making the parallel analysis of theoretical and experimental charge density to become common [START_REF] Koritsanszky | Chemical applications of X-ray charge-density analysis[END_REF][START_REF] Koritsanszky | Topological analysis of experimental electron densities. 1. The different C-C bonds in Bullvalene[END_REF][START_REF] Macchi | Experimental electron density in a transition metal dimer: metalmetal and metal-ligand bonds[END_REF][START_REF] Spackman | Charge densities from X-ray diffraction data[END_REF][START_REF] Souhassou | Topological analysis of experimental electron densities[END_REF][START_REF] Scherer | Molecular recognition in the solid state: topology of experimental and theoretical charge densities for Tetrasulfur Tetranitride[END_REF][START_REF] Messerschmidt | Atomic properties of N2O4 based on its experimental charge density[END_REF][START_REF] Mori-Sánchez | A classification of covalent, ionic, and metallic solids based on the electron density[END_REF][START_REF] Macchi | Chemical bonding in transition metal carbonyl clusters: complementary analysis of theoretical and experimental electron densities[END_REF][START_REF] Oddershede | Charge density study of naphthalene based on X-ray diffraction data at four different temperatures and theoretical calculations[END_REF][START_REF] Coppens | The interplay between experiment and theory in charge-density analysis[END_REF][START_REF] Messerschmidt | Electron density and bonding at inverted carbon atoms: an experimental study of a [1.1.1] propellane derivative[END_REF], especially as the QTAIM theory is rather independent from the basis set and the level of the quantum theoretical method used [START_REF] Jablonski | Basis set and method dependence in quantum theory of atoms in molecules calculations for covalent bonds[END_REF][START_REF] Matta | How dependent are molecular and atomic properties on the electronic structure method? Comparison of Hartree-Fock, DFT, and MP2 on a biologically relevant set of molecules[END_REF][START_REF] Rykounov | Quantitative estimates of transferability of the QTAIM descriptors. Case study of the substituted hydropyrimidines[END_REF].

The topological definition of a bonded interaction is based on the existence of a bond path (BP), the charge density being a maximum along the BP with respect to any neighboring line. BP is known as the atomic interaction line in the topological analysis of the electron density ρ(r) distribution. It is associated with all kinds of interactions, going from weak ones, such as intermolecular [START_REF] Scherer | Molecular recognition in the solid state: topology of experimental and theoretical charge densities for Tetrasulfur Tetranitride[END_REF][START_REF] Tsirelson | Topological definition of crystal structure: determination of the bonded interactions in solid molecular chlorine[END_REF], Van der Waals [START_REF] Gibbs | Role of directed van der Waals bonded interactions in the determination of the structures of molecular arsenate solids[END_REF], secondary ones between ions [START_REF] Luana | Ions in crystals: the topology of the electron density in ionic materials. II. The cubic alkali halide perovskites[END_REF][START_REF] Abramov | Secondary interactions and bond critical points in ionic crystals[END_REF], nonbonding [START_REF] Cioslowski | Universality among topological properties of electron density associated with the hydrogen-hydrogen nonbonding interactions[END_REF][START_REF] Matta | Hydrogen-hydrogen bonding: a stabilizing interaction in molecules and crystals[END_REF], and hydrogen bonds [START_REF] Koch | Characterization of CHO hydrogen bonds on the basis of the charge density[END_REF][START_REF] Espinosa | Hydrogen bond strengths revealed by topological analyses of experimentally observed electron densities[END_REF], to strong interactions, namely metal-metal [START_REF] Macchi | Chemical bonding in transition metal carbonyl clusters: complementary analysis of theoretical and experimental electron densities[END_REF][START_REF] Aray | Topology of the electron density and cohesive energy of the facecentered cubic transition metals[END_REF][START_REF] Gibbs | Electron density distributions calculated for the nickel sulfides millerite, vaesite, and heazlewoodite and nickel metal: a case for the importance of Ni-Ni bond paths for electron transport[END_REF][START_REF] Gervasio | About the topological classification of the metal-metal bond[END_REF], ionic [START_REF] Gervasio | About the topological classification of the metal-metal bond[END_REF][START_REF] Rincón | On the topology of the electron charge density at the bond critical point of the electron-pair bond[END_REF][START_REF] Zhang | Topology of electron charge density for chemical bonds from valence bond theory: a probe of bonding types[END_REF][START_REF] Hernández-Trujillo | Properties of atoms in molecules: atoms forming molecules[END_REF], and covalent bonds [START_REF] Souhassou | Topological analysis of experimental electron densities[END_REF][START_REF] Gervasio | About the topological classification of the metal-metal bond[END_REF][START_REF] Rincón | On the topology of the electron charge density at the bond critical point of the electron-pair bond[END_REF][START_REF] Zhang | Topology of electron charge density for chemical bonds from valence bond theory: a probe of bonding types[END_REF][START_REF] Hernández-Trujillo | Properties of atoms in molecules: atoms forming molecules[END_REF][START_REF] Cremer | Chemical bonds without bonding electron density-does the difference electrondensity analysis suffice for a description of the chemical bond?[END_REF][START_REF] Macdougall | Atomic properties and the reactivity of carbenes[END_REF], and also other kinds of uncommon bonding, for instance charge-shift bonding [START_REF] Rincón | On the topology of the electron charge density at the bond critical point of the electron-pair bond[END_REF][START_REF] Zhang | Topology of electron charge density for chemical bonds from valence bond theory: a probe of bonding types[END_REF][START_REF] Wu | The inverted bond in [1.1.1] propellane is a charge-shift bond[END_REF]. For intermolecular interactions, the Laplacian of the electron density Ñ 2 𝜌(r) allows one to define Lewis acid and base sites [START_REF] Tsirelson | Topological definition of crystal structure: determination of the bonded interactions in solid molecular chlorine[END_REF] and reveal directional 'key-lock' interactions corresponding to molecular recognition [START_REF] Scherer | Molecular recognition in the solid state: topology of experimental and theoretical charge densities for Tetrasulfur Tetranitride[END_REF], which contributes to construct layered structures [START_REF] Wong | The intensities of the infrared-active intermolecular translational bands in solid chlorine. Evidence for intermolecular bonding[END_REF]. The investigation of the energy densities at the bond critical point (BCP) and of ρ(r) and Ñ 2 𝜌(r) for solids and noble gas, offers recognition of van der Waals interactions as the result of a weak accumulation of electron density between the nuclei, leading to small binding energy [START_REF] Gibbs | Role of directed van der Waals bonded interactions in the determination of the structures of molecular arsenate solids[END_REF][START_REF] Hernández-Trujillo | Properties of atoms in molecules: atoms forming molecules[END_REF]. The ionic secondary interactions (e.g. alike ions in halides), caused by a large cation/anion size ratio and small unit cell, correspond, according to the analysis of existing BCPs, to energetically stabilized nonbonding repulsive interactions [START_REF] Luana | Ions in crystals: the topology of the electron density in ionic materials. II. The cubic alkali halide perovskites[END_REF][START_REF] Abramov | Secondary interactions and bond critical points in ionic crystals[END_REF][START_REF] Cioslowski | Universality among topological properties of electron density associated with the hydrogen-hydrogen nonbonding interactions[END_REF][START_REF] Matta | Hydrogen-hydrogen bonding: a stabilizing interaction in molecules and crystals[END_REF] and have properties at the BCP similar to that of closed-shell interaction of hydrogen bonds [START_REF] Koch | Characterization of CHO hydrogen bonds on the basis of the charge density[END_REF][START_REF] Espinosa | Hydrogen bond strengths revealed by topological analyses of experimentally observed electron densities[END_REF]. The metal-metal bonds in bulk metals have flat ρ(r) in the valence region and own a partial covalence degree [START_REF] Macchi | Chemical bonding in transition metal carbonyl clusters: complementary analysis of theoretical and experimental electron densities[END_REF][START_REF] Aray | Topology of the electron density and cohesive energy of the facecentered cubic transition metals[END_REF][START_REF] Gibbs | Electron density distributions calculated for the nickel sulfides millerite, vaesite, and heazlewoodite and nickel metal: a case for the importance of Ni-Ni bond paths for electron transport[END_REF][START_REF] Gervasio | About the topological classification of the metal-metal bond[END_REF]. The bond metallicity can be evaluated with the ratio xb=ρb/Ñ 2 rb, b standing for the BCP [START_REF] Jenkins | Direct space representation of metallicity and structural stability in SiO solids[END_REF][START_REF] Jenkins | Bond metallicity of materials from real space charge density distributions[END_REF]. The typical ionic bonds and covalent bonds are pure closed-shell interactions and shared-shell interactions, respectively. The polarization of bonds can be described by the deviation of the BCP from the midpoint [START_REF] Zhang | Topology of electron charge density for chemical bonds from valence bond theory: a probe of bonding types[END_REF] and the deviation of ρb from cylindrical symmetry, the latter deviation being defined by the bond ellipticity value (e=l1/l2)-1, with l1 and l2 the principal curvatures of ρb [START_REF] Souhassou | Topological analysis of experimental electron densities[END_REF][START_REF] Macdougall | Atomic properties and the reactivity of carbenes[END_REF]. The Laplacian distribution can state that ionic binding and covalent one are generated by the charge localized on one of the nuclei and an increased density equally shared between the nuclei, respectively [START_REF] Bader | Molecular charge distributions and chemical binding[END_REF]. The charge-shift bonding has a large ρb and a large positive Ñ 2 rb, which makes this interaction unclassifiable by the standard criteria [START_REF] Rincón | On the topology of the electron charge density at the bond critical point of the electron-pair bond[END_REF][START_REF] Zhang | Topology of electron charge density for chemical bonds from valence bond theory: a probe of bonding types[END_REF][START_REF] Wu | The inverted bond in [1.1.1] propellane is a charge-shift bond[END_REF].

However, the chemical bonding analysis by the QTAIM tool is limited by two problems. One is the Laplacian distribution of heavy elements and transition metals missing the complete shell structure of isolated atom, either because the last atomic shell is not resolved or Ñ 2 r(r) lacks charge concentration region as it is always positive there. The other is the sign of Ñ 2 r(r) belonging to the intermediate region between regions of pure closed-shell interactions and shared-shell interactions, which is quite indeterminate due to diffuse atomic valence density, causing low r(r) and Ñ 2 r(r) magnitudes in the bonding regions [START_REF] Gatti | Chemical bonding in crystals: new directions[END_REF][START_REF] Oganov | Computational Materials Discovery[END_REF]. Therefore, using the simple criterion of Ñ 2 r(r) at one point to characterize or classify the bonding in these two cases becomes particularly deceiving for intermediate region.

In this paper, we investigate the relations between the integral distribution of atomic interactions (Valence Shell Charge Concentrations) combined with the local virial theorem and the energy densities (local properties) at the bond critical point in order to propose a method to directly characterize the bonding interactions from the local properties. The density functional theory (DFT) has been used to calculate the Laplacian of the electron density for the outermost valence region of heavy atoms. And, in order to characterize and classify a large panel of bonds, the analysis of chemical bonding by the QTAIM tool has been carried out on various chemical systems going from molecules to ternary solid compounds.

II. Computational Methods

Density functional theory (DFT) calculations were performed using the QUANTUM ESPRESSO (QE) simulation package [START_REF] Giannozzi | QUANTUM ESPRESSO: a modular and open-source software project for quantum simulations of materials[END_REF][START_REF] Giannozzi | Advanced capabilities for materials modelling with Quantum ESPRESSO[END_REF]. The electronic exchange-correlation energy was treated by the generalized gradient approximation (GGA) using the Perdew-Burke-Ernzerhof (PBE) functionals [START_REF] Perdew | Generalized gradient approximation made simple[END_REF] and the interaction between ions and core electrons was described by the projector augmented wave (PAW) method [START_REF] Blöchl | Projector augmented-wave method[END_REF]. The scalar relativistic corrections have been accounted for in the PAW pseudopotentials as most of the relativistic effects on the electron density topology can be recovered at this level of theory [START_REF] Eickerling | Relativistic Effects on the Topology of the Electron Density[END_REF]. The electron density for all the systems of interest was calculated with a kinetic energy cutoff for wavefunctions of 48 Ry and the Monkhorst-Pack procedure was used to generate k-points for the Brillouin-zone sampling. For the molecular system H2O2, calculations were also performed with the ORCA program (version 4.2.1) [START_REF] Neese | The ORCA program system[END_REF][START_REF] Neese | Software update: the ORCA program system, version 4.0[END_REF] at the Hartree-Fock level with both the STO-3G and Def2-TZVPPD atomic basis sets [START_REF] Hehre | Self-Consistent Molecular-Orbital Methods. I. Use of Gaussian Expansions of Slater-Type Atomic Orbitals[END_REF][START_REF] Weigend | Balanced basis sets of split valence, triple zeta valence and quadruple zeta valence quality for H to Rn: Design and assessment of accuracy[END_REF][START_REF] Weigend | Accurate Coulomb-fitting basis sets for H to Rn[END_REF][START_REF] Rappoport | Property-optimized Gaussian basis sets for molecular response calculations[END_REF], and at the B3LYP, PBE and the reference CCSD(T) levels with the Def2-TZVPPD ones.

The electron density was subsequently analyzed with the program Critic2 [START_REF] Otero-De-La-Roza | Critic2: A program for real-space analysis of quantum chemical interactions in solids[END_REF] that implements Bader's Quantum Theory of Atoms in Molecules (QTAIM). In this work, the model used in Critic2 for the kinetic energy density G(r) calculation is based on the Thomas-Fermi equation with the semi-classical gradient correction proposed by Kirzhnits [START_REF] Kirzhnits | Quantum corrections to the Thomas-Fermi equation[END_REF][START_REF] Kirzhnits | Field theoretical methods in many-body systems[END_REF]. On this basis, Abramov [START_REF] Abramov | On the possibility of kinetic energy density evaluation from the experimental electron-density distribution[END_REF] proposed a simple approximate expression for directly relating G(r) to r(r):

𝐺(𝑟) = ! "# (3𝜋 $ ) ! " 𝜌(𝑟) # " + " %$ [∇((*)] ! -(.) + " / ∇ $ 𝜌(𝑟) (1)
In spite of a weak accuracy for typical shared interactions of eq.( 1), this equation gives a relatively accurate description in the medium-range distance (≈ 1-4 a.u., from BCP to nucleus) of G(r). It was found that the G(r) values from eq.( 1) are nearly quantitative for closed-shell interactions [START_REF] Espinosa | Hydrogen bond strengths revealed by topological analyses of experimentally observed electron densities[END_REF][START_REF] Espinosa | Experimental electron density overlapping in hydrogen bonds: topology vs. energetics[END_REF]. However the accuracy of eq.( 1) can become weak for typical shared interactions [START_REF] Gatti | Chemical bonding in crystals: new directions[END_REF], as will be confirmed hereafter in the case of H2O2. The local virial theorem [START_REF] Bader | Atoms in molecules: a quantum theory[END_REF] describes the effects of chemical bonding by local energy densities through Ñ 2 r(r):

" 0 ∇ $ 𝜌(𝑟) = 2𝐺(𝑟) + 𝑉(𝑟) (2)
𝐺(𝑟) + 𝑉(𝑟) = 𝐻(𝑟) (3)
where G, V and H are the kinetic, potential and total energy densities, respectively. Accordingly, the analysis of Ñ 2 r(r) gives evidence of charge concentration (Ñ 2 r(r)<0) or depletion (Ñ 2 r(r)>0) in the bonding region without resorting to a reference density. The charge depletion can also lead to a local charge accumulation when |V(r)|/G(r)>1, which gives rise to a relatively stable bonding dominated by the potential energy. The V(r) virial field dominated by the potential energy density in a system is the virial of the Ehrenfest force exerted on the electron density. Combining the virial theorem of energy with force, H(r)<0 and H(r)>0 indicate stable bonding and pure closed-shell interaction, respectively [START_REF] Hernández-Trujillo | Properties of atoms in molecules: atoms forming molecules[END_REF][START_REF] Gatti | Chemical bonding in crystals: new directions[END_REF][START_REF] Cremer | A description of the chemical bond in terms of local properties of electron density and energy[END_REF].

Thus, the properties of H(r) or H(r)/r(r) can provide a good compensation for the weakness of the Laplacian distribution for a specific interaction.

On the basis of the properties of Laplacian distribution and total energy density, the local properties at the BCP can be used to analyze a series of interactions in solids or crystals between pure closed-shell interactions and shared-shell interactions. According to eq.( 3),

1 $ -$ = 2 $ -$ (1 - |4 $ | 2 $ ) (4)
when Ñr vanishes at BCP, Gb, Vb and Hb are only related to rb and Ñ 2 rb from eq.( 1) and eq.( 2). Eq.( 4)

displays the variation of H(r)/r(r) along with |Vb|/Gb: the former indicator, the bond degree first introduced by Espinosa [START_REF] Espinosa | From weak to strong interactions: A comprehensive analysis of the topological and energetic properties of the electron density distribution involving X-H⋯ F-Y systems[END_REF], stands for the total energy per electron related to the total electronic pressure, the latter one exhibits the competition between potential energy and kinetic energy for bonding formation. These two indicators corresponding to specific characteristics of bonding can be used for the bonding classification. At the same time, the kinetic energy per electron Gb/rb is related to the variation tendency of Hb/rb vs |Vb|/Gb, which is also an important parameter for classification of bonding [START_REF] Gervasio | About the topological classification of the metal-metal bond[END_REF][START_REF] Gatti | Chemical bonding in crystals: new directions[END_REF][START_REF] Espinosa | From weak to strong interactions: A comprehensive analysis of the topological and energetic properties of the electron density distribution involving X-H⋯ F-Y systems[END_REF]. We shall mention that, eq.( 4) is valid only if the Kirzhnits approximation holds.

For the CuSbSe2 compound, in the calculation of the energies densities, we have used both the optimized electron density and the promolecular one, which consists in the sum of atomic densities (IAM -independent atom model).

III. Results and Discussion

III.1. Electron density and its Laplacian distribution in chemical bondings

According to radial density function calculations, in the periodic table from Sc to Ge, the Laplacian distribution of the N shells becomes indistinguishable from that of the M ones [START_REF] Shi | The shell structure of atoms and the Laplacian of the charge density[END_REF], and the outermost atomic shell charge concentration of transition metals are missing. Many methods have been considered to explore this problem and without exception they all have encountered the same situation, e.g. in Co [START_REF] Macchi | Experimental electron density in a transition metal dimer: metalmetal and metal-ligand bonds[END_REF][START_REF] Götz | Bond analysis of metal-element interactions in molecules and solids applying embedding and density functional techniques[END_REF],

Fe [START_REF] Macchi | Chemical bonding in transition metal carbonyl clusters: complementary analysis of theoretical and experimental electron densities[END_REF][START_REF] Götz | Bond analysis of metal-element interactions in molecules and solids applying embedding and density functional techniques[END_REF], Cr and Cd [START_REF] Macchi | Chemical bonding in transition metal carbonyl clusters: complementary analysis of theoretical and experimental electron densities[END_REF], Cu [START_REF] Aray | Topology of the electron density and cohesive energy of the facecentered cubic transition metals[END_REF][START_REF] Frenking | The nature of the bonding in transition-metal compounds[END_REF], W [START_REF] Frenking | The nature of the bonding in transition-metal compounds[END_REF], Ti, Mn, Ni and Mo [START_REF] Götz | Bond analysis of metal-element interactions in molecules and solids applying embedding and density functional techniques[END_REF].

Fig. 1 depicts the Laplacian distribution of bulk Cu [START_REF] Morozkin | Ce-Cu-Sb system at 670/870[END_REF] calculated from DFT-PAW based method that shows a four shells structure corresponding to charge concentration and depletion, with the spherical outermost valence shell regions of neighbouring atoms intersecting with each other and giving rise to an interconnected valence shell charge concentration (VSCC) along the BP confined in a volume with a convex lens shape. This highly delocalized network of valence regions is responsible for the binding in the metallic system and for its conductive properties. The characteristics of metal-metal bond are then fully displayed by the Laplacian distribution map.

Although from As to Kr the M and N shells are separated, the sign of the Laplacian indicates that the outermost shell is charge depleted [START_REF] Macchi | Experimental electron density in a transition metal dimer: metalmetal and metal-ligand bonds[END_REF][START_REF] Shi | The shell structure of atoms and the Laplacian of the charge density[END_REF]. Similar trends of lacking the outermost charge concentration region were observed for the subsequent rows [START_REF] Sagar | The Laplacian of the charge density and its relationship to the shell structure of atoms and ions[END_REF]. Further investigations with the DFT-PAW method show that the Laplacian distribution of both the nearest Se neighbours and second-nearest Se ones in metalloid bulk Se [START_REF] Akahama | Structural studies of pressure-induced phase transitions in selenium up to 150 GPa[END_REF] exhibits a separation of the outer valence regions into two shells (Fig. 2). The charge mostly corresponds to a localized accumulation slightly towards the inner shell, leading to inconspicuous charge concentration in the outermost spherical shell and quite indeterminate sign of the Laplacian there.

Interestingly, the VSCC of nearest Se neighbours present a butterfly-type pattern around the BCP with a continuous charge concentration at the BCP induced by nearby parts of two spherical valence regions, reflecting a covalent character, and wings constituted of two localized valence regions. This bonding exemplifies the fulfilment of the virial equilibrium (|Vb|/Gb≈2, Tab.1) for a covalent bond dominated by the potential energy in the whole interatomic region (Fig. 2(a)). In the interaction between second-nearest Se neighbours, the local charge accumulates along the BP though away from the BCP (Fig. 2 The distributions of Ñ 2 r(r) and H(r) have also been calculated for heavier elements of the fifth row by DFT-PAW method. The outermost spherical valence regions are displayed for bulk metalloid Sb [START_REF] Lomnytska | Phase equilibria in the V-Ni-Sb system[END_REF] in All the above calculations have been performed using plane waves and the energy densities using the Kirzhnits approximation. However, as shown in Ref [START_REF] Gatti | Chemical bonding in crystals: new directions[END_REF], this approximation is weakly accurate for shared interactions for in vacuo systems, the deviation reaching up to 300% in some cases. Therefore, in order to validate our results, we have performed additional calculations for H2O2 using localized molecular orbital approach, which allows us to obtain nearly true energy densities. The results are given in Table 1.

The Laplacian value obtained with the state-of-the-art reference CCSD(T) method amounts to 0.017856 e.Å -5 whereas that of B3LYP is intermediate between the latter and that obtained with PBE. This shows that, the exact exchange interaction is an important ingredient to obtain accurate electron density curva- Due to the absence of shared interaction in the inorganic solids investigated hereafter, the energy densities have been calculated in the realm of the Kirzhnits approximation. Gb, Vb and Hb are determined from the following methods: a Kirzhnits approximation. b HF/STO-3G. c HF/Def2-TZVPPD. d B3LYP/Def2-TZVPPD. e PBE/Def2-TZVPPD. f CCSD(T)/Def2-TZVPPD. The units are: electrons/bohr 3 for rb, electrons/bohr 5 for Ñ 2 rb, Hartree/bohr 3 for Vb, Gb and Hb and Å for distances.

III.2. Analysis of chemical bondings using energy densities at the bond critical point

The energy density parameters Hb/rb, |Vb|/Gb, Gb/rb at bond critical points are referred in this work as local properties. These parameters are linked together by eq.( 4), which can be regarded, when Gb/rb is constant, as an affine equation y=a0+a1.x, with y= Hb/rb and x=|Vb|/Gb. Then the corresponding straight line passes through the point (1, 0) and its slope satisfies the relation |a1|=a0= Gb/rb. Some examples for bonds in molecules and complexes are given in Fig. 5(a). As can be seen, the H-F bonds, both for isolated molecule and in complexes, and Li-C bonds in methyllithium polymers obey this affine relation. Since the number of electrons in bonding molecular orbital linearly decreases when the interatomic distance increases (see Fig. 5(b)), at least around the bond equilibrium state, the slope |a1| of these lines is related to the evolution of the charge density, which corresponds to a deformation of the electronic shells. The delineation of the electronic shell results from an accommodation between potential and kinetic energies that can be regarded as a pressure exerted on an electron by the other electrons or by an electron on the other ones, respectively. Therefore the slope |a1| reflects resistance to deformation of the electronic shells (reciprocal of polarizability) under pressure and can be considered as the rigidity of the interaction between atoms. This statement agrees with the larger Gb/rb ratio reported in literature for pure closed-shell interaction [START_REF] Hernández-Trujillo | Properties of atoms in molecules: atoms forming molecules[END_REF][START_REF] Gatti | Chemical bonding in crystals: new directions[END_REF][START_REF] Oganov | Computational Materials Discovery[END_REF][START_REF] Espinosa | From weak to strong interactions: A comprehensive analysis of the topological and energetic properties of the electron density distribution involving X-H⋯ F-Y systems[END_REF][START_REF] Bader | The characterization of atomic interactions[END_REF]. Hence for a specific interaction that bears a specific polarization, the linear characteristic of Hb/rb vs |Vb|/Gb reflects a linear evolution between deformation of charge distribution and interatomic distance, the Gb/rb ratio being related to the polarization of the interaction. Larger Gb/rb ratio (|a1|) corresponds to greater charge separation and as a consequence to lower polarizability.

In general, the bonding environment is more complex in solids or crystals due to their complex structures, not only related to bond lengths but also to other factors, such as coordination. (Fig. 8) that if charge transfer occurs at point 4, this feature hardly happens at point 3.

A comparison between interactions at point 1 and 2 (Fig. 9), both dominated by the kinetic energy in the bonding region (Fig. 7 (a)), shows a more pronounced closed-shell character at point 1, being farther away from the point (1, 0). Indeed the algebraic distance from BCP to the point (1, 0) in the map relating Hb/rb to |Vb|/Gb corresponds to the degree of closed-shell interaction for the negative values and to the charge sharing magnitude for the positive ones. In order to check that eq.( 4) allows for detecting similar bonding environments instead of depending only on the interatomic distance, we have also calculated the electron density using the independent atom model (IAM) for CuSbSe2 and determined the corresponding local energies densities. The results are depicted in Fig. 10 together with those obtained with the relaxed electron density (SCF). As can be seen, for identical bond distances, the absolute value of the slope Gb/rb differs from SCF to IAM. This shows that, Gb/rb is solely related to the electron density.

IV. Conclusion

The complete Laplacian shell structure of heavy elements and transition metals has been obtained by calculating the charge density using DFT-PAW approach. By combining the distributions of r(r) and H(r)

with local properties (energy densities at bond critical point) of interatomic interactions, the Cu-Cu metal bonding, Se-Se bonding in bulk Se, Sb-Sb bonding in bulk Sb and O-O charge-shift bonding in H2O2 have been characterized in the real space. This analysis has also been done for chemical bonding in molecules, binary oxides and ternary semiconducting compounds. Specific interactions in a system having similar bonding environment solely determined by interatomic distance presents a linear characteristic of Hb/rb vs |Vb|/Gb, the slope Gb/rb being related to the polarizability of the charge distribution and hence to the rigidity of the interaction between the atoms. Hence the energy density analysis at the bond critical point can be used as a rapid method to determine characteristics of a chemical bonding, namely the bonding state, the polarizability and the deformation of the charge distribution.

  (b)), resulting in extremely weakly negative Hb and |Vb|/Gb close to 1 (Tab.1). Combined with the dispersive H(r) distribution, it can be figured out to be a closed-shell interaction without charge transfer, and relatively stable as dominated by the potential energy (Fig.2(b)). This interaction could be related to a key-lock arrangement of the Se lone-pairs, similar to that reported in GeSe by Sist et al.[START_REF] Sist | High-Temperature crystal structure and chemical bonding in thermoelectric germanium selenide[END_REF].

Figure 1 .

 1 Figure 1. Laplacian distribution of Cu-Cu metal bonding in bulk Cu. Green and blue contour curves stand for positive and negative values, respectively. 'b' corresponds to the bond critical point.

Figure 2 .

 2 Figure 2. Distributions of Ñ 2 r(r) (top) and H(r) (bottom) of Se-Se bonding in bulk Se: (a) nearest neighbours; (b) second-nearest neighbours. Colour code: see Figure 1.

Fig. 3 .

 3 Fig.3. The Laplacian distribution of nearest Sb neighbours shows some charge accumulation between adjacent valence regions around the BCP (Fig.3(a)), while the positive values of Ñ 2 rb and |Vb|/Gb<2 (see Tab.1) are arguments against the classification of this bonding in the shared-shell interaction type. This statement is confirmed from Fig.3(a), which allows us to suggest that the charge accumulation around the BCP for the nearest Sb-Sb bonding does not originate from a real, shared charge density but from the diffusion of very close outermost shell charge concentrations. Regarding the second-nearest Sb neighbours (Fig.3(b)), in spite of a wide H(r) distribution between the atoms, the VSCCs are away from the interatomic surface. This behavior is similar to that described above for Se: the charge density depletion could be due to a key-lock arrangement of the lone-pairs. Moreover, the second-nearest Se-Se bonding indicates a more contracted charge accumulation towards the BP than the second-nearest Sb-Sb bonding despite the fact that both have very close values of rb (Tab.1).

Figure 3 .

 3 Figure 3. Distributions of Ñ 2 r(r) (top) and H(r) (bottom) of Sb-Sb bonding in bulk Sb: (a) nearest neighbours; (b) second-nearest neighbours.

Figure 4 .

 4 Figure 4. Distributions of Ñ 2 r(r) (top) and H(r) (bottom) of O-O bonding in H2O2 molecule.

Figure 5 .Fig. 6 )

 56 Figure 5. (a) Hb/rb vs |Vb|/Gb for H-F and Li-C bonding; (b) number of electrons in bonding molecular orbital (BMO) vs d(H⋯F). R 2 and a1 are the regression coefficient and the slope of the fitted line, respectively. The numerical data are from literature Ref. 57 and Ref. 59.

Figure 6 .

 6 Figure 6. Hb/rb vs |Vb|/Gb for As-O bonding. The numerical data are from literature Ref. 18.

Figure 7 .

 7 Figure 7. (a) Hb/rb vs |Vb|/Gb of Sb-Se bonding in compounds of the Cu-Sb-Se system; (b) algebraic distance of BCPs to the point (1, 0) in Fig.7(a) vs d(Sb⋯Se).

Figure 8 .

 8 Figure 8. Distribution of Ñ 2 r(r) (top) and H(r) (bottom) of Sb-Se bonding: (a) and (b) corresponding to points 3 and 4 in Fig.7, respectively.

Figure 9 .

 9 Figure 9. Distribution of Ñ 2 r(r) (top) and H(r)/r(r) (bottom) of Sb-Se bonding: (a) and (b) corresponding to points 1 and 2 in Fig.7, respectively.

Figure 10 .

 10 Figure 10. Hb/rb vs |Vb|/Gb for Sb-Se bonding in CuSbSe2. IAM and SCF stand for the independent atom model and self-consistent field, respectively. The numerical values (in Å) correspond to the related interatomic distances.

  tures. The Hartree-Fock level yields a negative Laplacian value at the BCP (O-O b and O-O c in Table 1), which is obviously wrong and caused by the lack of electronic correlation. Compared to B3LYP (O-O

d ), PBE (O-O e ) and CCSD(T) (O-O f ) energy densities, those obtained with the Kirzhnits approximation (O-O a ) are about 100% off. However, the signs of the values given by this approximation agree with those of the reference values, therefore qualitative interpretations of VSCC can be conducted with this approximation.

Table 1 .

 1 Energy density parameters at BCPs

	Interac-	rb	Ñ 2 rb	Gb	Vb	Hb	Hb/rb	Gb/rb	|Vb|/ Gb	Dis-
	tion Cu-Cu	tance 0.040387 0.044567 0.019501 -0.029949 -0.010448 -0.258697 0.482853 1.535767 2.552
	Se-Se 1	0.089750 -0.045870 0.051443 -0.103206 -0.051764 -0.576758 0.573181 2.006220 2.420
	Se-Se 2	0.020081 0.040622 0.011030 -0.011904 -0.000874 -0.043524 0.549275 1.079238 3.235
	Sb-Sb 1	0.049389 0.005384 0.019986 -0.038627 -0.018640 -0.377412 0.404665 1.932703 2.945
	Sb-Sb 2	0.020743 0.008917 0.005982 -0.009736 -0.003753 -0.180929 0.288386 1.627549 3.444
	O-O a	0.270780 0.146054 0.349791 -0.663068 -0.313278 -1.156860 1.291696 1.895614 1.465
	O-O b	0.328205 -0.302567 0.227321 -0.530284 -0.302963 -0.923091 0.692619 2.332754 1.396
	O-O c	0.344644 -0.330036 0.226887 -0.536284 -0.309396 -0.897727 0.658323 2.363657 1.386
	O-O d	0.278853 0.066722 0.194687 -0.372694 -0.178006 -0.638352 0.698170 1.914321 1.449
	O-O e	0.267436 0.127763 0.191311 -0.350682 -0.159371 -0.595920 0.715353 1.833043 1.464
	O-O f	0.270155 0.017856 0.183455 -0.362446 -0.178991 -0.662548 0.679072 1.975667 1.460

nearest neighbors.

second-nearest neighbors.

ACKNOWLEDGMENTS

The authors are grateful to Pr. A. Otero De La Roza for his advices regarding technical aspects of Critic2 program and its usage. This work is financially supported by China Scholarship Council (CSC). This work was granted access to the HPC resources of the Centre Informatique National de l'Enseignement Supérieur (CINES), Montpellier, France under allocation A0050806881 made by the Grand Equipement National de Calcul Intensif (GENCI). It was also granted access to the HPC resources of Aix-Marseille Université financed by the project Equip@Meso (ANR-10-EQPX-29-01) of the program "Investissements d'Avenir" supervised by the Agence Nationale de la Recherche.

AUTHOR INFORMATION

Corresponding Author *(P.B.) E-mail: pascal.boulet@univ-amu.fr.

DECLARATION OF COMPETING INTEREST

The authors declare no competing financial interest.


Amanvon Ferdinand Atta
email: amanvon.atta@inphb.ci

Bernard Cousin
email: bernard.cousin@irisa.fr

Joël Christian Adépo
email: joel.adepo@uvci.edu.ci

Souleymane Oumtanaga
email: souleymane.oumtanaga@inphb.ci

Light-tree Reconfiguration without Flow Interruption in a Sparse Wavelength Converter Network

Keywords: Light-tree Reconfiguration, Flow Interruption, Wavelength Converter, Flow Migration, Optical Network

Network reconfiguration is an important task in WDM optical networks, which enables the optimisation of network resources. With the growing demand for multicast applications (e.g., distance learning, IPTV), this study focuses on the reconfiguration of the routing of a multicast connection. In this study, the path of the multicast connection is represented by a light-tree. A light-tree reconfiguration consists of migrating an optical flow from a light-tree to a new one. However, it is very difficult to automate light-tree reconfiguration without flow interruption. Flow interruption is undesirable for network operators. Therefore, the problem studied here is to find a sequence of operations in order to migrate an optical flow from a light-tree to a new one without flow interruption in a sparse wavelength converter network. For solving the light-tree reconfiguration problem, we 1 Light-tree Reconfiguration without Flow Interruption propose a method based on a sub-tree approach. The comprehensive simulation results demonstrated the effectiveness of our method.

Introduction

A WDM network is made of optical nodes interconnected by WDM links. Wavelength Division Multiplexing (WDM) technology [START_REF] Brackett | Dense wavelength division multiplexing networks: principles and applications[END_REF] divides the bandwidth of an optical fiber into several wavelength channels [Pandya, 2020b], so that several users can transmit data at different wavelengths through the same fiber simultaneously. Hence, the WDM network is the dominant type of network to fulfil the bandwidth requirements of applications [START_REF] Bajpai | Energy-efficient and spectral-efficient mixed line rate optical WDM networks: a comparison[END_REF]. In addition, wavelength conversion is a technique that can reduce the probability of blocking in a network using WDM [START_REF] Subramaniam | All-optical networks with sparse wavelength conversion[END_REF]]. This technique is made possible by the use of a node component called a wavelength converter. A wavelength converter is a node component that takes a signal at a given wavelength as an input and converts it into a signal using another wavelength [START_REF] Iness | Sparse Wavelength Conversion in Wavelength-Routed WDM Optical Networks[END_REF]. Due to the high cost of this node component [START_REF] Petale | Optimal of wavelength converter deployment in wdm optical networks[END_REF], in practice network operators equip a limited number of optical nodes with wavelength converters [START_REF] Zakouni | Wavelength assignment vs. wavelength converter placement in wavelength-routed optical WDM networks[END_REF]. A WDM optical network in which only some optical nodes in the network are capable of performing wavelength conversion is called a sparse wavelength converter network [START_REF] Pinto-Roa | Multi-objective routing and wavelength converter allocation under uncertain traffic[END_REF]. In this network, two types of connections are allowed: unicast (point-to-point) and multicast (pointto-multipoint) connections.

Multicast is an effective technique for simultaneously transmitting information from one source to multiple destinations. Most multicast applications such as weather forecasts, online video games, online banking, video conferencing and IPTV are increasingly popular with users [CISCO, 2020[START_REF] Pradhan | A heuristic approach based on dynamic multicast traffic grooming in WDM mesh networks[END_REF]. In order to support multicast in WDM optical networks, some requirements from both the data plane (hardware) and the control plane (software) must be satisfied. On the data plane, ideally, each optical node (also called a node) in the network would possess light splitters [START_REF] Das | Shufflecast: An optical, data-rate agnostic and low-power multicast architecture for next-generation compute clusters[END_REF]. A light splitter is a node component that can split an optical signal (also called an optical flow) into two or more outgoing links [START_REF] Yang | Optimal and heuristic algorithms for all-optical group multicast in resource-constrained wdm networks[END_REF]. In this work, we assume that each network node is equipped with light splitters because a light splitter is relatively inexpensive [START_REF] Lin | Design of Light-Tree Based Optical Inter-Datacenter Networks[END_REF]. On the control plane, a routing solution must be computed to transfer an optical flow from one source node to multiple destination nodes. A typical routing solution is a light-tree, which is a point-to-multipoint all-optical path established in the network [START_REF] Zhou | Joint optimization for multicast provisioning in mixed-line-rate optical networks with a column generation approach[END_REF]. This type of all-optical path is created by allocating the same wavelength on every link of the tree.

Changes in traffic demand by users, network failures (at nodes or links) and the deployment of new network resources can force a network operator to re-optimize the allocation of network resources [START_REF] Li | Survey of WDM network reconfiguration: topology migrations and their impact on service disruptions[END_REF]Wu, 2015, Wu, 2011]. To do this, the network operator may have to configure new paths with some optical resources in order to transfer an optical flow and release some optical resources used by the working paths: it is said that the network operator reconfigures the network.

Network reconfiguration is widely considered one of the most important tasks in all types of WDM networks [START_REF] Wu | A survey of WDM network reconfiguration: Strategies and triggering methods[END_REF]. Indeed, it allows the network operator to meet the ever-increasing needs of users while effectively managing its limited resources. A reconfiguration task can be performed either on unicast connections or on multicast connections or on both connections. The reconfiguration of unicast connections has been extensively studied in recent years according to the survey in [START_REF] Li | Survey of WDM network reconfiguration: topology migrations and their impact on service disruptions[END_REF]. In addition, given the growing demand for multicast applications, we focus on multicast connection reconfiguration.

Let one multicast connection be established by a light-tree (called a working light-tree) on which an optical flow passes through a network. The problem of multicast connection reconfiguration studied here consists of migrating the optical flow (or flow) from the working light-tree to a new pre-calculated light-tree without flow interruption from a source node toward one or more destination nodes. Flow interruption is not recommended because the network operator must reimburse the customers concerned by flow interruption with a penalty [START_REF] Valentini | Network resiliency against earthquakes[END_REF]. This reconfiguration problem becomes difficult to solve because some resources (i.e. wavelength channels) required by the new light-tree are already allocated to the working light-tree [START_REF] Adépo | Tree Reconfiguration with Network Resources Constraint[END_REF] and some are not. This dependency between some resources of both light-trees requires going through one or more transient light-trees using spare wavelengths and some operations such as wavelength conversion to avoid flow interruption [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF]. Wavelength conversion cannot be performed on all nodes because in a sparse wavelength converter network, some nodes do not have wavelength converters. A spare wavelength is a wavelength not required by the set of all established routes (including the working light-tree) and the new light-tree [START_REF] Khanam | An offline cost-efficient strategy for multicast traffic protection in WDM optical mesh networks to aid rapid recovery[END_REF]. As the wavelength is a valuable resource, our method should use spare wavelengths parsimoniously.

To date, some methods of light-tree reconfiguration using a so-called branch approach [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF] have been proposed to migrate a flow from a working light-tree to a new light-tree without flow interruption and within a reasonable computation time while using spare wavelengths as few as possible. However, the branch approach is not adapted if only a small number of network nodes are capable of performing wavelength conversion. Therefore, we propose a method using a sub-tree approach. The key contributions of this paper are summarized as follows:

1. Identification of categories of sub-tree pairs from a pair of light-trees.

2. For each category of sub-tree pairs, an algorithm is proposed to find the sequence of operations required to reconfigure a sub-tree pair belonging to this category. 3. A Sub-tree by Sub-tree (i.e. Sub-tree approach) Reconfiguration Algorithm denoted by SbSRA to solve light-tree reconfiguration problem.

The remainder of this paper is organized as follows. Section 2, presents the operations that can be used to configure an optical node. Section 3 presents the formal specification of the problem. Section 4 discusses the related works. Section 5 explains the contributions of this study in detail. The evaluation of our work is presented in Section 6. Section 7 concludes our work.

Fundamental concepts

In this section, we first present the set of operations [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF] used in reconfiguration process of a light-tree pair, then some definitions that are useful for understanding the remainder of this paper.

Operations for node configuration:

The six operations that can be used for node configuration are the following :

1. The addition of wavelength switching on node x is denoted by ADD(x pi,{po1,...,p ok } wi

), configures node x by adding it, the capability to switch an optical flow of wavelength w i received by its input port p i to multiple output ports (i.e. {p o1 , ..., p ok }) without changing wavelength w i . In other words, this operation notifies node x to switch a given optical flow from one input port to one or multiple output ports. 2. The deletion of wavelength switching on node x is denoted by DEL(x pi,{po1,...,p ok } wi

), configures node x by deleting it, the capability to switch an optical flow of wavelength w i received by its input port p i to multiple output ports (i.e. {p o1 , ..., p ok }) without changing wavelength w i . In other words, this operation notifies node x to not longer switch a given optical flow from one input port to one or multiple output ports. 3. The wavelength conversion on node x is denoted by CONV(x ). For an optical flow of wavelength w i arriving at the input port p i of node x and outgoing to its output port p o1 , this operation allows the changeover of the optical flow from p o1 to multiple output ports (i.e. {p o2 , ..., p ok }) on the wavelength w o . The wavelength w i may be different from the wavelength w o . 5. The convergence on node x is denoted by CONVG(x ). Non-convergence is the operation that cancels the effect of the convergence operation. In other words, it guarantees that the flow of wavelength w i enters only through the input port p i2 (stopping the flow from entering by p i1 ) without changing the output ports (i.e. {p o1 , ..., p ok }).

It is important to note that the multi-changeover operation is the atomic combination of the deletion of wavelength switching and either the addition of wavelength switching or wavelength conversion. Also, a bad sequencing of these six operations can interrupt the flow.

Definition 1 ST is a sub-tree of the tree T if it connects a node of T to one or more other nodes of T . Branch B of tree T rooted at node r is the segment of T that connects r to a leaf node of T . Therefore, a branch is a particular type of sub-tree.

Definition 2 A changeover node is a node on which the multi-changeover operation can be applied.

Definition 3 A wavelength channel or channel denoted by (x, po x , w i )-> (y, pi y , w i ) is a fiber link that connects node x to node y and on which a wavelength w i is busy on the output port po x of node x and on the input port pi y of y. A wavelength semi-channel or semi-channel (x, pox, -) -> (y, piy, w i ) is a fiber link that connects x to y on which a wavelength w i is free on an output port pox of x and busy on the input port piy of y.

Definition 4 The pre-establishment of a sub-tree consists of preparing it to transport a flow by configuring all the nodes of this sub-tree. In other words, just after having pre-established a sub-tree, no flow is yet passing through it. In fact, a pre-established sub-tree contains at least one semi-channel at its root.

3 Problem specification

System model and assumptions

A sparse wavelength converter network is modeled as an undirected graph G(V, E). V is the set of network nodes and E is the set of network links. V = V c ∪V c , where V c and V c represent respectively the set of nodes that do not have the wavelength conversion capability and the set of nodes that have the wavelength conversion capability. Let C(r, D, w c ) be a multicast connection established in the network by using wavelength w c . Node r is the source node of connection C and D is the set of destination nodes of this connection. Also, w c is a wavelength that belongs to the set of wavelengths W usable in each link of the network. The working light-tree used to transmit the optical flow from node r to the elements of D is modeled by a tree denoted by T 0 = (V 0 , E 0 ) , rooted at r and spanning D. With V 0 ⊆ V , E 0 ⊆ E, r ∈ V 0 and D ⊆ V 0 \ {r}. The new pre-calculated light-tree (using the same wavelength as the new lighttree) to which the flow is to be migrated is also modeled by a tree denoted by

T f = (V f , E f ), rooted at r and spanning D. With V f ⊆ V , E f ⊆ E, r ∈ V f and D ⊆ V f \ {r}.
Our model assumes that each network node has the full capability of splitting the optical signal and the set of spare wavelengths W s is not empty, with W s ⊂ W .

Problem formulation

The problem of light-tree reconfiguration, which consists of migrating (an optical) flow from the working light-tree T 0 to the pre-calculated new light-tree T f is equivalent to find a sequence of light-trees < T 0 , T 1 , T 2 , ..., T f -1 , T f >. Indeed, T 0 and T f share some wavelength channels. In other words, to establish T f , it is necessary to establish some wavelength channels already assigned to T 0 . This situation of sharing wavelength channels can be compared with the coding problem when the two values of two variables have to be swapped. The solution to this problem involves the use of an transient variable (here an transient wavelength channel that can use a spare wavelength) to assign the value of a variable (here a wavelength channel of T 0 ) to another variable (here a wavelength channel of T f ). Note that each transient light-tree of the light-tree sequence to be found is composed by a set of transient wavelength channels. At step i of the reconfiguration process, The set of transient wavelength channels is obtained by applying configuration operations on at least one node of V i-1 ∪V f , where V i-1 is the set of nodes of the light-tree T i-1 . T i-1 represents the current light-tree. Therefore, our problem is to find a sequence of configuration operations. Note that the current light-tree is the light-tree that is used to transmit an optical flow at a given step. Thus, in the first step, the current light-tree is the working light-tree. In the rest of this paper, a configuration operation is called an operation. In summary, the problem can be formulated as follows:

• Given : The working light-tree T 0 on which the flow passes, the new lighttree T f on which the flow is to be transferred at the end of reconfiguration.

• Our goal : Find the sequence of operations TREE OP SEQ =< O 1 , O 2 , ..., O k-1 , O k > which if
it is executed, it permits the migration of an optical flow from T 0 to T f without flow interruption and within a reasonable computation time while using as few spare wavelengths as possible.

With O k , the k-th operation to be executed.

Related works

The problem of reconfiguring multicast routing in WDM networks has not yet been sufficiently addressed as mentioned in the survey [START_REF] Wu | A survey of WDM network reconfiguration: Strategies and triggering methods[END_REF]. In [Luekijna and Saivichit, 2007], the authors proposed some methods to find a new optimal light-tree to transfer an optical flow. One of the pioneering work was carried out in [START_REF] Perényi | Regular reconfiguration of light-trees in multilayer optical networks[END_REF]. The authors solved the problem of reconfiguring trees where the leaves of the tree change dynamically. However, all works aforementioned does not address how to switch the flow from one light-tree to another without flow interruption.

For reconfiguring unicast routing in connection-oriented networks without flow interruption, Make-Before-Break (MBB) [START_REF] Coudert | Reconfiguration of the routing in wdm networks with two classes of services[END_REF] is one of the most widely used policies. MBB consists of first pre-establishing the new path, then switching the flow to the new path before releasing the resources used by the old path [START_REF] Jaumard | Efficient Real-Time Scalable Make-Before-Break Network Re-Routing[END_REF]. In the context of multicast routing reconfiguration, an adaptation of MBB called MBB 1 [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF] can be applied by considering each branch of the light-tree as a path. MBB 1 reconfigures a light-tree pair (a working light-tree, a new light-tree) by applying MBB for each pair of branches (old branch belonging to the working light-tree, new branch belonging to the new light-tree). However, if the branches of a pair of branches share wavelength channels then MBB 1 may induce an interruption of the flow. To remedy the flow interruption caused by MBB 1, some methods to solve the light-tree reconfiguration problem based on a branch approach [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF] have been proposed. This Branch approach uses an Elementary Reconfiguration Process (ERP) of each pair of branches (old branch, new branch). The old branch is a branch of the working light-tree and the new branch is a branch of the new light-tree. The elementary reconfiguration of a pair of branches consists of:

1. Choose a changeover node: the changeover node algorithm [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF] is proposed to select the changeover node which guarantees the continuity of the flow. 2. Use a spare wavelength w 1 to pre-establish the new branch from this changeover node. 3. At the changeover node, transfer the flow from the old branch to the new branch. 4. Delete the old branch (i.e. release the wavelength on the old branch).

Figure 1 describes the elementary reconfiguration process of a pair of branches on a reconfiguration problem instance. This instance (see Figure 1.a) concerns the multicast connection (s, {f, g}, w 0 ). The working (or initial) lighttree T 0 is represented by the set of links in solid red and the final (or new) light-tree T f by the set of links in solid blue. For this instance, only the pair of branches ({s{b{c{d{e{f }}}}}}, {s{d{f }}}) leading to node f needs to be reconfigured because the branch leading to node g is identical on both lighttrees. For the only pair of branches to be reconfigured, the changeover node chosen by ERP is b. Figures 1.b to 1.d highlight the steps 2 to 4 of the elementary reconfiguration process. In the rest of this paper, to simplify the notation of each operation, and without loss of generality, the input port and output ports are respectively replaced by the name of the parent node and the names of the child nodes on a tree. So ERP returns an operation sequence using spare wavelength w 1 denoted by ) >. Two methods based on the branch approach were proposed. These methods are BpBAR 1 [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF] and BpBAR 2 [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF]. These two methods carry out the reconfiguration process in two phases (i.e. a round trip). The elementary reconfiguration process is applied to each pair of branches (requiring reconfiguration) in the first phase using the spare wavelength w 1 and then again in the second phase using the wavelength w 0 requires by the new light-tree. The sequence of operations returned by the first phase of BpBAR 1 concerning the pair of branches leading to node f (see Figure 1.a) is equal to ERP w1 ({s{b{c{d{e{f }}}}}}, {s{d{f }}}). Second phase gives as output the sequence of operations ERP w0 ({s{b{c{d{e{f

ERP w1 ({s{b{c{d{e{f }}}}}}, {s{d{f }}}) =< ADD(s b,{d} w1 ), ADD(d s,{f } w1 ), ADD(f d,{-} w1 ), MULT CHG(b s,c,{s},
}}}}}}, {s{d{f }}}) = ¡ ADD(d s,{f } w0 ), ADD(f d,{-} w0 ), MULT CHG(s -,s,{s} w1,w0 ), DEL(s b,{d} w1 ), DEL(d s,{f } w1 ), DEL(f d,{-} w1
)¿. Thus, the sequence of operations requires to reconfigure this pair of branches is constituted by the sequence ERP w1 ({s{b{c{d{e{f }}}}}}, {s{d{f }}}) follows by the sequence ERP w0 ({s{b{c{d{e{f }}}}}}, {s{d{f }}}). The sequence of operations TREE OP SEQ returned by BpBAR 1 is the sequence of operations required by the pair of branches leading to node f because only this pair of branches requires reconfiguration. The nodes s and f are respectively the root node and the leaf node of this pair of branches. Therefore, the input port (respectively the output ports) cannot specified concerning ADD operations and MULT CHG operations (respectively DEL operations and ADD operations) on the node s (respectively on the node f ). This is expressed by a dash.

BpBAR 1 and BpBAR 2 allow reconfiguration without flow interruption of the multicast connexion. However, BpBAR 1 has a rather long reconfiguration time. To deal with this, BpBAR 2 performs some operations in parallel. BpBAR 1 and BpBAR 2 allow light-tree reconfiguration without flow interruption but can lead a rather high cost of spare wavelengths used.

In order to reduce the cost of using spare wavelengths, the TRwRC [START_REF] Cousin | Tree Reconfiguration without Lightpath Interruption in Wavelength Division Multiplexing Optical Networks with Limited Resources[END_REF] method was proposed. However, it can generate a rather long reconfiguration time because it generates a series of light-tree sets to be reconfigured. In order to improve TRwRC by reducing its reconfiguration time, the RCBRwPR [START_REF] Adépo | Tree Reconfiguration with Network Resources Constraint[END_REF] method was proposed. RCBRwPR proposed a sequence of operations to configure in parallel a set of branches and this operation sequence requires at least two different spare wavelengths at each step.

In summary, MBB 1 is an MBB-based method that generates flow interruption because it not appropriate if a pair of branches share links. Branch-based methods require that any changeover node (when it is different from the root of the light-tree pair) selected at a reconfiguration step has wavelength conversion capability. This requirement is not easy to satisfy in the context of a sparse wavelength converter network. For instance, in Figure 1.b, if node b does not have the wavelength conversion capability then no other node can be chosen as a changeover node. As a result, pre-establishment is not possible without flow interruption. Therefore, using a branch-based method for the light-tree reconfiguration may generate flow interruption in a sparse wavelength converter network. To our knowledge, no method has been proposed today for solving the light-tree reconfiguration problem in a sparse wavelength converter network.

Our contribution

For solving the formulated problem (see section 3.2), previous branch-based methods were proposed to find a sequence of operation sequences of every pair of branches from the light-tree pair to be reconfigured. However, the sequence of operations returned by a branch-based method generates flow interruption if a changeover node does not have wavelength conversion capability. Therefore, we propose a method based on a sub-tree approach. This approach consists of selecting sequentially a sub-tree pair from a pair of light-trees (current lighttree, new light-tree) and finding an operation sequence for this sub-tree pair. In the sub-tree approach, the changeover node of a sub-tree pair is either the root of the light-tree pair or a non-leaf node x of this light-tree pair such that node x has the wavelength conversion capability or not. We remind you that the current light-tree is the light-tree that is used to transmit an optical flow at a given step. Note that, this light-tree is equal to the working lighttree specified in section 3.2. The solution of our method is the sequence of the operation sequences required by each sub-tree pair. Because our method must use as few spare wavelengths as possible, the sub-tree pairs have been categorized. In the following subsections, we propose a categorization of subtree pairs and an algorithm to find an operation sequence for each category of sub-tree pairs. Then we propose an algorithm that takes as input a pair of light-trees and returns an operation sequence to reconfigure this pair.

Categorization of sub-tree pairs

At each step, a pair of sub-trees (ST c , ST f ) must be selected and the appropriate operation sequence for (ST c , ST f ) must be found. This sequence of operations should require as few spare wavelengths as possible. Note that execution of an operation sequence must make it possible to pre-establish the new sub-tree ST f (i.e. a sub-tree of the new light-tree T f ), to transfer the flow from the current sub-tree ST c (i.e. a sub-tree of the current light-tree T c ) to ST f and to delete ST c (i.e. to release the wavelength used by the wavelength channels of ST c ). A spare wavelength can be required for the pre-establishment of ST f . To use spare wavelengths the fewest times, the operations in the sequence should use a spare wavelength only if it is required. Depending on whether a spare wavelength is required, there are three possible sub-tree pair categories:

1. The category of sub-tree pairs with identical links: A pair of sub-trees (ST c , ST f ) belongs to this category if the links of the current sub-tree ST c are the same as the links of the sub-tree ST f . Such a sub-tree pair does not require to be reconfigured. Therefore, a spare wavelength is not required. 2. The category of sub-tree pairs with disjointed links: A pair of sub-trees (ST c , ST f ) belongs to this category if ST f does not share any links with ST c . Therefore, the pre-establishment of ST f does not require the use of a spare wavelength. 3. The category of sub-tree pairs with shared links: A pair of sub-trees (ST c , ST f ) belongs to this category if ST f shares links (but not all links) with ST c . Therefore, the pre-establishment of ST f requires the use of spare wavelengths.

In the following, for each of the two last categories of sub-tree pairs, we explain how to select1 a sub-tree pair of this category and how to find the sequence of operations required for this selected pair of sub-trees.

Reconfiguration of a sub-tree pair with disjointed links

Let (ST c , ST f ) be a selected sub-tree pair with disjointed links, where ST c is a sub-tree of the current light-tree T c and ST f a sub-tree of the new light-tree T f . This implies that (1) (ST c , ST f ) is rooted at a divergent node n. In addition, in order to avoid flow interruptions, it is necessary that ( 2)

CG(T c , T f ) c = CG(T c , T f ) f = CG(ST c , ST f ). Requirement (2) confers to
(ST c , ST f ) the property of non-interruption of the flow. CG(T c , T f ) c denotes the set of convergent nodes of the light-tree pair (T c , T f ) which belongs to ST c , CG(T c , T f ) f denotes the set of convergent nodes of the light-tree pair (T c , T f ) that belongs to ST f and CG(ST c , ST f ) denotes the set of convergent nodes of the light-tree pair (T c , T f ) which belongs to both ST c and ST f . By definition, a divergent node belongs to (T c , T f ) and has at least one child node on T c that is different from its child nodes on T f . By definition, a convergent node belongs to (T c , T f ) and its parent node on T c is different from its parent node on T f . In the remainder of this paper, we refer to Select SDL(T c , T f , n) as a function that implements the selection (refer to (1) and ( 2)) of the Sub-tree pair with Disjointed Links (SDL). For the light-tree pair (T c , T f ) and the divergent node n as input, Select SDL(T c , T f , n) returns (ST c , ST f ) with disjointed links that does not interrupt flow.

Reconf SDL (see Algorithm 1) finds an operation sequence to reconfigure the sub-tree pair with disjointed links (ST c , ST f ). We introduce some use- ful notations for a good understanding of the remainder of our work. Let Wavelength(T ) be the wavelength used by tree T , Parent(x, T ) be the input port that connect node x to its parent node on tree T , CHILD(x, T ) be the set of output ports that connects node x to its child nodes on tree T , IN(T ) be the set of intermediate nodes of tree T and Root(T 0 , T 1 ) be the common root node of tree T 0 and tree T 1 . Note that node x is an intermediate node of tree T if x is not the root node of T and CHILD(x, T ) is not empty. In short, to reconfigure the pair of sub-trees (ST c , ST f ) with disjointed links, Reconf SDL returns an operation sequence composed by : a set of ADD operations to be executed in parallel (1), a set of CONVG operations to be executed in parallel (2), a MULT CHG operation (3), a set of NCONVG operations to be executed in parallel ( 4) and a set of DEL operations to be executed in parallel (5). It is important to note that a set of operations added to SDL OP SEQ via the = operator (refer for instance to line 3 ) means that these operations must be executed in parallel. The execution of ( 1) and ( 2) should allow the preestablishment of the new sub-tree ST f . (3) allows the flow to be transferred from ST c to ST f . ( 4) and ( 5) delete the current sub-tree ST c . The sequence of operations returned by Algorithm 1 does not require a spare wavelength because ST c and ST f do not share links: the sequence of operations requires the same wavelength (i.e. w c ). In addition, this operation sequence is composed by several operations to be executed in parallel. Therefore, this sequence is fast to execute.

Reconfiguration of a sub-tree pair with shared links

Let (ST c , ST f ) be a sub-tree pair with shared links rooted at node n, where ST c is a sub-tree of the current light-tree T c and ST f a sub-tree of the new light-tree T f . This implies that (1) ∃ m ∈ CG(ST c , ST f ). In other words, the set of convergent nodes of the sub-tree pair (ST c , ST f ) is not empty. (2) n = First ancestor(m, T c , T f ) such as Dest(n, m, T c ) = Dest(n, m, T f ) and n ∈ V c . First ancestor(m, T c , T f ) is the youngest ancestor of node m on T c which is also an ancestor of node m on T f . Dest(n, m, T c ) (respectively Dest(n, m, T f )) is the set of destination nodes such that each element of this set has at least one ancestor on the segment of T c (respectively T f ) from n to m. We remind that V c is the set of network nodes such that each element of this set has wavelength conversion capability. Requirement (2) confers to (ST c , ST f ) the property of non-interruption of the flow. Note that if First ancestor returns null then the root node n of sub-tree pair (ST c , ST f ) is the root of the light-tree pair (T c , T f ). We refer to Select SSL(T c , T f , m) as a function that implements the selection (refer to (1) and ( 2)) of a Sub-tree pair with Shared Links (SSL). For the pair of light-trees (T c , T f ) and the convergent node m as input, Select SSL(T c , T f , m) returns (ST c , ST f ) with shared links that does not cause flow interruptions. The Reconf SSL function (See Algorithm 2) takes as input a pair of subtrees (ST c , ST f ) with shared links. Then it returns an operation sequence denoted by SSL OP SEQ that does not interrupt flow. ST f shares links with ST c , so its pre-establishment requires a spare wavelength denoted by w s . Let AVAILABLE(T 0 , T 1 ) be the set of available wavelengths that are common to ) ; 10: end for 11: Repeat line 3 to line 10 using now w c as the spare wavelength and w s as the current wavelength ; 12: Return SSL OP SEQ ;

T 0 and T 1 . Note that w s is randomly selected from AVAILABLE(ST c , ST f ). If SSL OP SEQ obtained at line 10 is executed, then ST f is configured using spare wavelength w s . However, ST f must use the same wavelength as ST c (i.e. w c ) : SSL OP SEQ is not complete. Therefore, line 11 completes SSL OP SEQ by successively repeating instructions from line 3 to line 10, considering that the spare wavelength is w c and w s is the current wavelength.

5.2 Sub-tree based method for light-tree reconfiguration

Proposed algorithm

We now propose a Sub-tree by Sub-tree Reconfiguration Algorithm denoted by SbSRA (see Algorithm 3) to solve the formulated problem. Let us reminder that the objective here is to find the sequence of operations, which if executed, it allows the migration of an optical flow from the working light-tree T 0 to the new light-tree T f without flow interruption and within a reasonable computation time while using as few spare wavelengths as possible. To do this, SbSRA sequentially selects a pair of sub-trees and finds an operation sequence appropriate for its reconfiguration. This ensures that at the end of Algorithm 3, SbSRA produces the sequence of the sequences of operations requires to reconfigure the pair of light-trees (T 0 , T f ), which is given as input of this algorithm.

This sequence denoted by TREE OP SEQ must require as few spare wavelengths as possible. Therefore, Algorithm 3 starts by selecting the pairs of Algorithm 3 Sub-tree by Sub-tree Reconfiguration Algorithm ( SbSRA) Input: T 0 , T f // T 0 : The working light-tree; T f : The new light-tree Output: TREE OP SEQ // The sequence of the sequences of operations 1: TREE OP SEQ = null. T c = T 0 ; // T c : The current light-tree 2: while DG(T c , T f ) != null do // DG(T c , T f ) : The list of unvisited divergent nodes of the light-tree pair (T c , T f )

3: n = First element of DG(T c , T f ) ; 4: (ST c , ST f ) = Select SDL(T c , T f , n) ; // (ST c , ST f ) : A sub-tree pair with disjointed links 5: if (ST c , ST f ) != (null,null) then 6: SDL OP SEQ = Reconf SDL(ST c , ST f ) ;
// An operation sequence to reconfigure the sub-tree pair (ST c , ST f ) with disjointed links 7:

TREE OP SEQ += SDL OP SEQ ; // SDL OP SEQ is appended to TREE OP SEQ 8:

T c = T c -ST c + ST f ; // ST f is added to T c and ST c is deleted from T c 9: end if 10: end while 11: while CG(T c , T f ) != null do // CG(T c , T f ) :
The list of unvisited convergent nodes of the light-tree pair (T c , T f ) T c = T c -ST c + ST f ; // ST f is added to T c and ST c is deleted from T c 17: end while 18: Return TREE OP SEQ ; sub-trees with disjointed links (which does not require spare wavelengths) and finding the appropriate operation sequence for each of them (refer from line 2 to line 10) while taking care to update TREE OP SEQ and the current light-tree T c at each iteration. Note that, at each iteration, the first unvisited divergent node that is the first child of the root of the light-tree pair (T c , T f ) is chosen as the root of the sub-tree pair with disjointed links to be selected. A divergent node is visited if it has been used for an iteration of the first loop. At the end of first loop (refer to line 10), if the light-tree pair (T c , T f ) does not contain at least one unvisited convergent node then Algorithm 3 stops. Otherwise, the instructions contained in the second loop (refer from line 11 to line 17) are executed to select each sub-tree pair with shared links and to compute its sequence of operations to complete TREE OP SEQ. Note that if no operation in TREE OP SEQ concerns a convergent node of (T c , T f ) then this convergent node is said unvisited.

12: m = First element of CG(T c , T f ) ; 13: (ST c , ST f ) = Select SSL(T c , T f , m) ; // (ST c , ST f ) : A sub-

Illustration of this algorithm

Let the problem instance shows in Figure 2.a. The set of links in solid red forms the working light-tree T 0 rooted at s. The set of links in solid blue forms the new light-tree T f rooted at s. Note that initially, the current light-tree T c is the working light-tree T 0 . The first loop (refer from line 2 to line 10) is executed as follows. The list of unvisited divergent nodes of the light-tree pair (T c , T f ) contains nodes k and d. Node k is the first divergent node which is a child node of the root node s. From divergent node k, Select SDL(T 0 , T f , k) returns ({k{i{l}}}, {k{n{l}}}), which is a sub-tree pair with disjointed links, where {k{i{l}}} is the current sub-tree ST c and {k{n{l}}} is the new sub-tree ST f . Then, Reconf SDL takes this pair of sub-trees as input and returns :

OP SEQ 1 = SDL OP SEQ =< {ADD(n k,{l} w0 )}, {CON V G(l {i,n},{-} w0 )}, M U LT CHG(k s,i,{n} w0,w0 ), {N CON V G(l {i,n},{-} w0 )}, {DEL(i k,{l} w0 )} >.
Then, OP SEQ 1 is appended to the sequence of the sequence of operations TREE OP SEQ. Figures 2.b to 2.d presents the execution of the sequence of operations OP SEQ 1 . The current light-tree is updated by replacing the current sub-tree with the new sub-tree in the current light-tree. The set of red and blue links forms (see Figure 2.d) the current light-tree T c at the end of the first iteration of the first repeat loop. The new list of unvisited divergent nodes of the light-tree pair (T c , T f ) contains only node {d}. Node g is the only convergent node descending from divergent node d on the current light-tree but does not descend from node d on the new light-tree. Therefore, From divergent node d, Select SDL(T c , T f , d) does not return a sub-tree pair with disjointed links: it is the end of the first loop of Algorithm 3 because all divergent nodes have been visited. The convergent node g has not yet been visited. Therefore, the second loop (refer from line 11 to line 17) is executed as follows. Select SSL(T c , T f , g) returns ({a{b{c{d{h, e{g{f }}}}}}}, {a{b{g{f }, c{d{h}}}}}) which is a subtree pair with shared links, where {a{b{c{d{h, e{g{f }}}}}}} is the current sub-tree ST c and {a{b{g{f }, c{d{h}}}}} is the new sub-tree ST f . Then, Reconf SSL takes as input this pair of sub-trees and returns the sequence of operations using the spare wavelength )} >. Note that the operations placed between brackets in OP SEQ 1 or OP SEQ 2 must be executed in parallel. Then, TREE OP SEQ =< OP SEQ 1 , OP SEQ 2 >. The current light-tree is updated (Figure 2.h). All convergent nodes have been visited : Algorithm 3 stops and returns the sequence of the sequences of operations TREE OP SEQ requires for all sub-tree pairs to be reconfigured. Semi-channel of working light-tree using wavelength w 0 Free link Semi-channel of new light-tree using wavelength w 0 Transient semi-channel using spare wavelength w 1 6 Performance study

Performance criteria

To determine the effectiveness of the proposed method, we compared our method (i.e., SbSRA) to RCBRwPR and MBB 1. Three criteria are used :

the duration of the reconfiguration process [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF], the cost of spare wavelengths [START_REF] Cousin | Tree reconfiguration without lightpath interruption in WDM optical networks[END_REF] and the average interruption rate. In the following, Seq(T 0 , T f ) denotes the sequence of operations obtained by any method. The duration of a reconfiguration sequence denoted by duration(Seq(T 0 , T f )) is the total duration of operation constituting Seq(T 0 , T f ). It is expressed by Equation (1):

duration(Seq(T 0 , T f )) = |Seq(T0,T f )|-1 k=0 duration(O k ) (1)
duration(O k ) is the duration of k-th operation contained in the sequence of operations Seq(T 0 , T f ). Without loss of generality, we assume that the duration of each O k is unitary. Therefore :

duration(Seq(T 0 , T f )) = |Seq(T 0 , T f )| (2)
In general, the execution of an operation contained in Seq(T 0 , T f ) allows either to create wavelength channels or to delete wavelength channels. These wavelength channels may use a spare wavelength. Let G k be the graph whose set of links E k represents the set of residual wavelength channels after the execution of the first k-th operations contained in Seq(T 0 , T f ). Therefore, the cost of spare wavelengths denoted by add cost(Seq(T 0 , T f )) is the total sum of spare wavelengths used by G k graphs:

add cost(Seq(T 0 , T f )) = |Seq(T0,T f )|-1 k=0 |Ws|-1 j=0 |E k | l=0 G w j s k,l (3)
where W s is the set of spare wavelengths (see section 3.1) that can be used in the reconfiguration process and

interrupt rate(O k ) = d∈D O k (d) |D| ( 4
)
where D is the set of destination nodes (see section 3.1) and

O k (d) = 1 if O k execution interrupts flow toward node d 0 otherwise.
Therefore, the average interruption rate caused by the execution of operation sequence seq(T 0 , T f ) is defined by Equation ( 5) :

interrupt rate(seq(T 0 , T f )) = |Seq(T0,T f )|-1 k=0 interrupt rate(O k ) |Seq(T 0 , T f )|
(5)

Experimental setup

Our simulations are based on three real network topologies (see Table 1) that are widely used in the field of optical network research [START_REF] Pavan | Generating Realistic Optical Transport Network Topologies[END_REF]: NSFNET, which has a small size, GEANT, which has a medium size and CORONET [The Internet Topology Zoo, 2019], which has a large size. Each real topology is represented by a graph G(V, E) implemented using Networkx [START_REF] Hagberg | Exploring network structure, dynamics, and function using networkx[END_REF], a python graph analysis package. V is the number of nodes and E is the number of links. Note that for each topology, the number of nodes that have the wavelength conversion capability |V c | is randomly selected (uniform law) belonging [1; |V | 2 [. Moreover, without loss of generality, we assume that each link (fiber) supports at most |W | wavelengths (|W | = 16).

For each topology, a Monte-Carlo simulation was run 5000 times to evaluate each performance criterion. One simulation consists of :

1. Randomly (uniform law) selects a node that is taken as the source node of a multicast connection. 2. Randomly (uniform law) selects a number of nodes that is used as the destination nodes of the multicast connection. 3. The working tree of the multicast connection is built by generating a tree of the shortest paths that spanning source and destination nodes using the Dijkstra algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]. 4. The new tree is built by generating a spanning tree of minimum weight using the Prim algorithm [START_REF] Prim | Shortest Connection Networks and some Generalizations[END_REF].

5. Both trees were assigned the same randomly selected wavelength (uniform law) in W . 6. This pair is used as an input by three methods : MBB 1, RCBRwPR and our method (i.e., SbSRA).

Analysis of Experimental Results

The results (Average (AVG), Standard Deviation (SD), Maximum (M) and Minimum (m)) of the performance criteria are listed in Table 2 to Table 4. The results of the performance evaluations noted in Table 2 show that all values concerned by our method ( SbSRA) are equal to zero regardless of a given real topology (NSFNET, GEANT, CORONET). This confirms that SbSRA permits light-tree reconfiguration without flow interruption in sparse wavelength converter network. But, this Table and Figure 3 show that MBB 1 and RCBRwPR interrupt the flow to a non-zero percentage of destinations: these methods caused flow interruption. In short, the performance study confirms that these last two methods are not usable for light-tree reconfiguration in sparse wavelength converter network. Table 3 shows that RCBRwPR provides the highest cost of spare wavelengths. This is due to the fact that this method requires to use at least two different spare wavelengths for the establishment of wavelength channels of the new light-tree while SbSRA requires to use a single spare wavelength and MBB 1 does not require a spare wavelength. In addition, Figure 4 and Table 3 show that the cost of spare wavelengths increases with the size of the network

Conclusion

In this work, we solve the problem, which consists of finding an operation sequence that allows an optical flow to be migrated from a working light-tree to a new light-tree without flow interruption and within a reasonable computation time while using the spare wavelengths as few as possible. Some methods based on the branch approach have been proposed previously. However, these methods are useful to solve the problem in the context where all nodes have the wavelength conversion capability. To our knowledge, no method had been proposed in the context where only some nodes have the wavelength conversion capability. In order to fill this lack of solution, we proposed the SbSRA, which is a method based on a sub-tree approach. In order to build the sequence of operations requires to solve the problem, SbSRA at first, adds in this sequence of operations, the sequence of operations requires by each sub-tree pair with disjointed links. Note that this kind of sub-tree pair does not require spare wavelengths. Next, if the sequence of operations is not complete then SbSRA adds in this sequence of operations, the sequence of operations requires by each sub-tree pair with shared links. Note that each sub-tree pair with shared (or disjointed) links selected has the property of non-interruption of the flow. Performance study has validated that our method is the only method that allows to reconfigure a pair of light-trees (working light-tree, new light-tree) without flow interruption in a sparse wavelength converter network. But on large networks, the duration of the reconfiguration and the cost of spare wavelengths may become not negligible. Therefore, in our future work, we will study the duration of the reconfiguration process and the cost of spare wavelengths could be further reduced.

Fig. 1

 1 Fig. 1 Elementary reconfiguration sequence

Algorithm 1

 1 Reconf SDL Input: ST c , ST f // ST c : The current sub-tree; ST f : The new sub-tree Output: SDL OP SEQ // the sequence of operations for (ST c , ST f ) reconfiguration 1: SDL OP SEQ = null. w c = Wavelength(ST c ) ; // w c : The current wavelength used by ST c 2: for each x ∈ IN(ST f ) do 3: SDL OP SEQ = ADD(x Parent(x,ST f ),CHILD(x,ST f ) wc ) ; 4: end for 5: for each x ∈ CG(ST c , ST f ) do // CG(ST c , ST f ) : The set of convergent nodes of (ST c , ST f ) 6: SDL OP SEQ = CON V G(x Parent(x,STc),Parent(x,ST f ),CHILD(x,STc) wc ) ; 7: end for 8: x = Root(ST c , ST f ) ; // x: The root node of (ST c , ST f ) and also the changeover node 9: SDL OP SEQ += M U LT CHG(x Parent(x,STc),CHILD(x,STc),CHILD(x,ST f ) wc,wc ) ; 10: for each x ∈ CG(ST c , ST f ) do 11: SDL OP SEQ = N CON V G(x Parent(x,STc),Parent(x,ST f ),CHILD(x,STc)) wc ; 12: end for 13: for each x ∈ IN(ST c ) do 14: SDL OP SEQ = DEL(x Parent(x,STc),CHILD(x,STc) wc ) ; 15: end for 16: Return SDL OP SEQ ;

Algorithm 2

 2 Reconf SSL Input: ST c , ST f Output: SSL OP SEQ // Operation sequence for (ST c , ST f ) reconfiguration 1: SSL OP SEQ = null. w c = Wavelength(ST c ) ; // w c : The current wavelength used by ST c 2: w s = Random(AVAILABLE(ST c , ST f )) ; // w s : A spare wavelength randomly selected 3: for each x ∈ V f do // V f : The set of non-root nodes of ST f 4: SSL OP SEQ = ADD(x Parent(x,ST f ),CHILD(x,ST f ) ws ) ; 5: end for 6: x = Root(ST c , ST f ) ; // x: The root node of (ST c , ST f ) and also the changeover node 7: SSL OP SEQ += M U LT CHG(x Parent(x,STc),CHILD(x,STc),CHILD(x,ST f ) ws,wc ) ; 8: for each x ∈ V c do // V c : The set of non-root nodes of ST c 9: SSL OP SEQ = DEL(x Parent(x,STc),CHILD(x,STc) wc

  = Reconf SSL(ST c , ST f ) ; // An operation sequence to reconfigure the sub-tree pair (ST c , ST f ) with shared links 15: TREE OP SEQ += SSL OP SEQ ; // SSL OP SEQ is appended to TREE OP SEQ 16:

  w 1 : OP SEQ 2 = SSL OP SEQ =< {ADD

  Figure 2.e to Figure 2.h give an execution view of OP SEQ 2 .

Fig. 2

 2 Fig. 2 A view of the sequence of operations execution

  l-th wavelength channel contained in G k used the spare wavelength w j s 0 otherwise. The interruption rate caused by execution of an operation O k denoted by interrupt rate(O k ) is the ratio of the number of destination nodes interrupted after the execution of O k to the total number of destinations. interrupt rate(O k ) is defined by Equation (4):

Fig. 3

 3 Fig. 3 Comparison of the average interruption rate

Fig. 5

 5 Fig. 5 Comparison of the average of duration

  to switch the optical flow of wavelength w i received on its input port p i to multiple output ports (i.e. {p o1 , ..., p ok }) after converting wavelength w i to another wavelength w o .

							pi,{po1,...,p ok } wi,wo	),
	configures node x 4. The multi-changeover	on	node	x	is	denoted	by
	MULT CHG(x	pi,po1,{po2,...,p ok } wi,wo

  Convergence allows the wavelength flow w i to converge to the same node x by two of its input ports (p i1 and p i2 ) without changing the output ports (i.e. {p o1 , ..., p ok }).

	6. The	non-convergence	on	node	x	is	denoted	by
	NCONVG(x	{pi1,pi2},{po1,...,p ok } wi
								{pi1,pi2},{po1,...,p ok } wi	).

Table 1

 1 Topology size

	Network	Number of nodes	Number of links
	NSFNET	14	21
	GEANT	40	75
	CORONET	75	99

Table 2

 2 Average interruption rate (%) caused by the three methods

			NSFNET			GEANT		CORONET
	Methods	AVG	SD	m/M	AVG	SD	m/M	AVG	SD	m/M
	SbSRA	0	0	0/0	0	0	0/0	0	0	0/0
	RCBRwPR	19.5	22.33	0/66	8.87	9.17	0/77	13.37	13.22	0/77
	MBB 1	25.72	16	2/83	20.69	13.75	0/96	44.38	21.95	2/96

Reader can see more details about the selection of sub-tree pairs here : https://hal. archives-ouvertes.fr/hal-02374828

Light-tree Reconfiguration without Flow Interruption (so with the size of light-trees) for methods RCBRwPR and SbSRA. This finding is correct because, Equation (3) shows that the cost of spare wavelengths increases with the size of light-trees and the number of spare wavelengths used during the reconfiguration process. Table 4 and Figure 5 show that MBB 1 has the highest duration. These results are due to the fact that at each reconfiguration step, MBB 1, RCBRwPR and SbSRA permits to reconfigure respectively the nodes of a single pair of branches, the nodes of a set of branch pairs and the nodes of a single sub-tree pair.