Anthony Phimphachanh

Joseph Chamieh

Laurent Leclercq

Simon Harrisson

Mathias Destarac

Patrick Lacroix-Desmazes

Corine Gérardin

Martin In
email: martin.in@umontpellier.fr

Hervé Cottet
email: herve.cottet@umontpellier.fr

Characterization of diblock copolymers by capillary electrophoresis: From electrophoretic mobility distribution to distribution of composition

Free solution capillary-electrophoresis (CE) is a powerful separation technique for the characterization of diblock copolymers. In this work, four series of double-hydrophilic anionic and cationic block copolymers, namely, poly(acrylamide)-block-poly(acrylic acid) (PAM-b-PAA), poly(acrylamide)-block-poly((3-acrylamidopropyl)trimethylammonium chloride) (PAM-b-PAPTAC), poly(ethylene oxide)-block-poly(acrylic acid) (PEO-b-PAA) and poly(poly(ethylene glycol) methyl ether acrylate)-block-poly(acrylic acid) (P(PEGA)-b-PAA), were synthesized by reversible additionfragmentation chain transfer (RAFT) polymerization and characterized by CE. The electrophoretic mobility distributions of the copolymers were transformed into distributions of composition ratio by introducing a retardation parameter, Xexp,, that represents the hydrodynamic drag retardation due to the neutral block of the copolymer. A linear correlation between Xexp and the ratio of the degrees of polymerization of each blocks was experimentally established and was consistent with the model of electrophoretic mobility of composite macromolecules with hydrodynamic coupling. Finally, the comparison of the distributions between the different copolymer families was significantly improved by considering the distributions in composition ratio compared to the electrophoretic mobility distributions, since it takes into account the differences in solvation, expansion and drag force according to the chemical nature of the blocks.

Introduction

The characterization of diblock copolymers by separation techniques is challenging but of primary importance to check their purity and to characterize their distributions in size and in chemical composition. [START_REF] Thevarajah | Quantifying the Heterogeneity of Chemical Structures in Complex Charged Polymers through the Dispersity of Their Distributions of Electrophoretic Mobilities or of Compositions[END_REF] Block copolymers prepared by reversible deactivation radical polymerization frequently contain homopolymer impurities. [START_REF] Morel | Electrophoretic Behavior of Amphiphilic Diblock Copolymer Micelles[END_REF][START_REF] Sutton | Purity of Double Hydrophilic Block Copolymers Revealed by Capillary Electrophoresis in the Critical Conditions[END_REF] These include dead chains from termination reactions during polymerization of the first block, as well as the products of side-reactions such as chain transfer to solvent or monomer during polymerization of the second block. The growth of the second block in copolymer synthesis is often evidenced by a decrease of the elution time in size-exclusion chromatography (SEC) as a result of the increased hydrodynamic radius [START_REF] Javakhishvili | Neutral, Anionic, Cationic, and Zwitterionic Diblock Copolymers Featuring Poly(2-methoxyethyl acrylate)"Hydrophobic" Segments[END_REF][START_REF] Delplace | Nitroxide-Mediated Radical Ring-Opening Copolymerization: Chain-End Investigation and Block Copolymer Synthesis[END_REF] . However, this only holds if the second block contributes significantly to the hydrodynamic radius of the diblock copolymer. Getting more quantitative information can be challenging especially in aqueous SEC. Different solvation properties between the blocks of a block copolymer can lead to coelution of polymers of different mass in SEC, resulting in inaccuracy in the obtained molar masses. [START_REF] Nejad | Synthesis of Methacrylate Derivatives Oligomers by Dithiobenzoate-RAFT-Mediated Polymerization[END_REF] Additionally, interactions with the stationary phase 3 may lead to HPLC-type elution which is dependent on the chemical composition of the polymer as well as its size. For diblock copolymer SEC, particular elution conditions are generally required and size distributions should be expressed in terms of hydrodynamic radius (and not molar mass) due to the difference in chemical composition / solvation of the two blocks [START_REF] Nejad | Synthesis of Methacrylate Derivatives Oligomers by Dithiobenzoate-RAFT-Mediated Polymerization[END_REF] . The proportion of each monomer in a copolymer can be obtained by liquid chromatography under critical conditions LCCC, also known as LC-PEAT, for the point of exclusion-adsorption transition for neutral blocks [START_REF] Jacquin | Controlling the Melting of Kinetically Frozen Poly(butyl acrylate-b-acrylic acid) Micelles via Addition of Surfactant[END_REF][START_REF] Jacquin | Characterization of Amphiphilic Diblock Copolymers Synthesized by MADIX Polymerization Process[END_REF] .

The critical conditions for LCCC (or LC-PEAT) are usually difficult to find and are very sensitive to small changes in mobile phase composition and/or temperature.

An alternative separation technique for charged copolymers is free solution capillary electrophoresis (CE) [START_REF] Morel | Electrophoretic Behavior of Amphiphilic Diblock Copolymer Micelles[END_REF][START_REF] Sutton | Purity of Double Hydrophilic Block Copolymers Revealed by Capillary Electrophoresis in the Critical Conditions[END_REF][START_REF] Jacquin | Controlling the Melting of Kinetically Frozen Poly(butyl acrylate-b-acrylic acid) Micelles via Addition of Surfactant[END_REF][START_REF] Jacquin | Characterization of Amphiphilic Diblock Copolymers Synthesized by MADIX Polymerization Process[END_REF][START_REF] Jacquin | Self-Assembly of Charged Amphiphilic Diblock Copolymers with Insoluble Blocks of Decreasing Hydrophobicity: From Kinetically Frozen Colloids to Macrosurfactants[END_REF] . The electrophoretic separation of charged homopolymers from diblock copolymers is generally easily obtained in free solution CE. Moreover, for self-assembling diblock copolymers, CE can also separate micelles from unimers [START_REF] Morel | Electrophoretic Behavior of Amphiphilic Diblock Copolymer Micelles[END_REF][START_REF] Jacquin | Controlling the Melting of Kinetically Frozen Poly(butyl acrylate-b-acrylic acid) Micelles via Addition of Surfactant[END_REF][START_REF] Jacquin | Characterization of Amphiphilic Diblock Copolymers Synthesized by MADIX Polymerization Process[END_REF] and allows studying the impact of added surfactant on the copolymer micelles [START_REF] Morel | Electrophoretic Behavior of Amphiphilic Diblock Copolymer Micelles[END_REF][START_REF] Jacquin | Controlling the Melting of Kinetically Frozen Poly(butyl acrylate-b-acrylic acid) Micelles via Addition of Surfactant[END_REF] . In the presence of cationic blocks, experimental difficulties arise from polymer adsorption onto the wall of silica based capillaries. The characterization of cationic diblock copolymers requires the use of a neutrally coated [START_REF] Sutton | Purity of Double Hydrophilic Block Copolymers Revealed by Capillary Electrophoresis in the Critical Conditions[END_REF] , or positively charged capillary [START_REF] Anik | Determination of Polymer Effective Charge by Indirect UV Detection in Capillary Electrophoresis: Toward the Characterization of Macromolecular Architectures[END_REF] .

Another challenging issue in the characterization of diblock copolymers by CE is to extract the distribution in composition of the copolymers from the electropherogram. Raw electropherograms can be transformed into distributions of effective mobility, or of any other related parameter, provided that the relationship between effective mobility and the considered parameter is known [START_REF] Chamieh | Quantitative Analysis in Capillary Electrophoresis: Transformation of Raw Electropherograms Into Continuous Distributions[END_REF] . The determination of polymer dispersity via the variance of the chemical composition distribution [START_REF] Chamieh | Quantitative Analysis in Capillary Electrophoresis: Transformation of Raw Electropherograms Into Continuous Distributions[END_REF] or via the calculation of the ratio of moments of the distribution has also been studied [START_REF] Thevarajah | Quantifying the Heterogeneity of Chemical Structures in Complex Charged Polymers through the Dispersity of Their Distributions of Electrophoretic Mobilities or of Compositions[END_REF] . A key point to achieve such electropherogram transformation is to have a reliable relation between the effective mobility of the diblock copolymer and the degrees of polymerization of each block and thus, to the chemical composition of the copolymer [START_REF] Sutton | Purity of Double Hydrophilic Block Copolymers Revealed by Capillary Electrophoresis in the Critical Conditions[END_REF] . The electrophoretic mobility of a diblock copolymer is generally expressed as a weighted average of the mobilities of different subunits constituting the copolymer [START_REF] Long | Electrophoretic Mobility of Composite Objects in Free Solution: Application to DNA Separation[END_REF] . The choice of the subunits and the corresponding weights have been described in the literature as depending on the conformations of each block and on the hydrodynamic coupling regime between the two blocks 12-15 . More recently, Chubynsky and Slater studied in more detail the "end-effect" (i.e. the fact that the ends of the copolymer chain are more hydrodynamically exposed to the solvent) [START_REF] Chubynsky | Theory of End-Labeled Free-Solution Electrophoresis: Is the End Effect Important?[END_REF] and the effect of polymer stiffness on the electrophoretic modeling [START_REF] Chubynsky | Electrophoresis of Heteropolymers. Effect of Stiffness[END_REF] . The electrophoretic models of composite objects [START_REF] Long | Electrophoretic Mobility of Composite Objects in Free Solution: Application to DNA Separation[END_REF][START_REF] Long | Simultaneous Action of Electric Fields and Nonelectric Forces on a Polyelectrolyte: Motion and Deformation[END_REF] which are relevant for diblock copolymers, were also applied to end-labeled free solution electrophoresis (ELFSE) [START_REF] Vreeland | Molar Mass Profiling of Synthetic Polymers by Free-Solution Capillary Electrophoresis of DNA-Polymer Conjugates[END_REF][START_REF] Nedelcu | Branched Polymeric Labels Used as Drag-Tags in Free-Solution Electrophoresis of ssDNA[END_REF] , which consists in attaching a monodisperse neutral block (drag-tag) to a polydisperse biopolyelectrolyte (for instance, for DNA sequencing in free solution [START_REF] Nedelcu | Branched Polymeric Labels Used as Drag-Tags in Free-Solution Electrophoresis of ssDNA[END_REF][START_REF] Desruisseaux | Electrophoresis of Composite Molecular Objects. 1. Relation between Friction, Charge, and Ionic Strength in Free Solution[END_REF] ), or conversely, in attaching a monodisperse polyelectrolyte to a polydisperse neutral polymer (for instance, for sizebased neutral polymer characterization [START_REF] Vreeland | Molar Mass Profiling of Synthetic Polymers by Free-Solution Capillary Electrophoresis of DNA-Polymer Conjugates[END_REF] ). In this way, the dependence of electrophoretic mobility with the molar mass of the end-labelled composite object is obtained in free solution due to the variation of the charge-to-friction ratio.

Double-hydrophilic block copolymers (DHBC) are block copolymers containing two hydrophilic segments. DHBCs on their own are completely soluble in water and do not self-assemble in dilute conditions. DHBCs can still retain an amphiphilic character and this can lead to self-organization at the meso-scale in concentrated conditions [START_REF] Schmidt | Double Hydrophilic Block Copolymer Self-Assembly in Aqueous Solution[END_REF] . They can undergo morphological transitions induced by external stimuli [START_REF] Guragain | Multi-Stimuli-Responsive Polymeric Materials[END_REF] in dilute solution. The great development of reversible deactivation radical polymerization [START_REF] Perrier | 50th Anniversary Perspective: RAFT Polymerization-A User Guide[END_REF][START_REF] Matyjaszewski | Atom Transfer Radical Polymerization[END_REF][START_REF] Nicolas | Nitroxide-Mediated Polymerization[END_REF][START_REF] Destarac | Industrial Development of Reversible-Deactivation Radical Polymerization: is the Induction Period Over?[END_REF] in the last two decades allows tailoring the stimuli-responsiveness (e.g. to changes in pH, temperature, ionic strength, or light) of these polymers by controlling both the nature of monomers and the degree of polymerization of the blocks. When one block is a polyelectrolyte, DHBCs can undergo micellization by electrostatic complexation in the presence of an oppositely charged polyelectrolyte. These properties lead to a wide range of applications such as control of crystallization of inorganic compounds [START_REF] Colfen | Double-Hydrophilic Block Copolymers: Synthesis and Application as Novel Surfactants and Crystal Growth Modifiers[END_REF] , drug delivery [START_REF] Loh | Triply Triggered Doxorubicin Release From Supramolecular Nanocontainers[END_REF] or template for ordered mesoporous materials [START_REF] Baccile | Ecodesign of Ordered Mesoporous Materials Obtained with Switchable Micellar Assemblies[END_REF] . For this last application of DHBC, the asymmetry ratio, defined as the ratio of degrees of polymerization of both blocks, is of crucial interest since it determines the structure of the DHBC-templated mesoporous materials.

It is the aim of the present work to characterize the composition of DHBC by CE, with particular attention to the asymmetry ratio. The approach has been applied to series of anionic and cationic In the next section, different models for the electrophoretic mobility of composite objects such as block copolymers are briefly reviewed. In the third section, the synthesis of the copolymers and the experimental conditions of their characterization by CE are reported. The results of this work are presented in section 4, where we describe a method to transform the distribution of electrophoretic mobility into a distribution of the ratio of degree of polymerization of both blocks.

Mobility of diblock copolymers constituted of a polyelectrolyte and a neutral block

In this section, we present different possible electrophoretic mobility models that are relevant for diblock copolymers composed of a polyelectrolyte part attached to a neutral polymer coil. These theoretical models were developed by Desruisseaux et al [START_REF] Desruisseaux | Electrophoresis of Composite Molecular Objects. 2. Competition between Sieving and Frictional Effects in Polymer Solutions[END_REF] , building on previous work by Long et al. [START_REF] Long | Electrophoretic Mobility of Composite Objects in Free Solution: Application to DNA Separation[END_REF][START_REF] Long | Simultaneous Action of Electric Fields and Nonelectric Forces on a Polyelectrolyte: Motion and Deformation[END_REF] Figure 1 shows the different possible conformations that can be encountered for DHBC, corresponding to the different models presented below.

Model 1: hydrodynamic coupling

In Model 1, hydrodynamic coupling between the polyelectrolyte part and the neutral coil is taken into account. ) depends on the polyelectrolyte persistence length, and thus, on the ionic strength. Equation (1) neglects the so-called end-effect [START_REF] Chubynsky | Theory of End-Labeled Free-Solution Electrophoresis: Is the End Effect Important?[END_REF] . Please note that subscript and superscript 0 refer to the polyelectrolyte block, for consistency with ref 28.

Models without hydrodynamic coupling

Model 2: polyelectrolyte chain in coil conformation

Model 2 in Figure 1 corresponds to the segregation of the neutral polymer coil from the polyelectrolyte coil. In the absence of hydrodynamic coupling between the two parts, and if the polyelectrolyte chain does not stretch during electrophoresis (i.e. at sufficiently low electric field), the electrophoretic mobility of the DHBC, ,2 diblock ep  , is given by the average electrophoretic mobility of the two parts weighted by their hydrodynamic friction coefficient [START_REF] Long | Electrophoretic Mobility of Composite Objects in Free Solution: Application to DNA Separation[END_REF] . Using Stokes equation for spherical objects, ,2 diblock ep  is expressed as [START_REF] Long | Simultaneous Action of Electric Fields and Nonelectric Forces on a Polyelectrolyte: Motion and Deformation[END_REF][START_REF] Desruisseaux | Electrophoresis of Composite Molecular Objects. 2. Competition between Sieving and Frictional Effects in Polymer Solutions[END_REF] :

1 0 0 ,2 1 0 0 1 i i ep ep diblock i ep neutral h i i h R R            (2)
where i  is the friction coefficient of the i th part constituting the DHBC, neutral h R is the hydrodynamic radius of the neutral coil, 0 h R is the hydrodynamic radius of the polyelectrolyte block.

Model 3: polyelectrolyte chain in fully stretched conformation

When the polyelectrolyte coil is stretched under the concomitant influence of the electric field and the opposed drag force due to the presence of the neutral coil, it can reach a fully extended conformation as depicted in Figure 1 (Model 3). Stokes law is no longer appropriate for the frictional coefficient of the polyelectrolyte chain, and the electrophoretic mobility of the DHBC, ,3

diblock ep



, is given by [START_REF] Baccile | Ecodesign of Ordered Mesoporous Materials Obtained with Switchable Micellar Assemblies[END_REF] :

1 0 0 ,3 1
0 0 0 0 2 1 ln h i i ep ep diblock i ep neutral i i R DP b DP            ( 3
)
where b0 is the size of a charged monomer in the polyelectrolyte chain. Equation (3) assumes that the friction coefficient rod γ of the stretched polyelectrolyte cylinder is averaged on all orientations relative to the flow direction, and is given by:

0 0 rod 0 3π b DP γ ln(DP )   (4)
where  is the viscosity of the solvent.

Even if the electrical field is not strong enough to stretch the polyelectrolyte block (hydrodynamic segregation), the polyelectrolyte contour length may still be shorter than the persistence length of the polyelectrolyte. In this situation, the segregation between the neutral and the polyelectrolyte parts is sterically obtained, but the electrophoretic mobility is still described by equation (3) 27 .

Experimental

Chemicals

Ammonium persulfate (APS, 98%) and sodium formaldehyde sulfoxylate dehydrate (NaFS, 98%) were purchased from Acros organics. Poly(ethylene glycol) methyl ether acrylate (Mn = 480 g/mol, 8.5 EO units on average) and (3-acrylamidoprpyl)trimethylammonium chloride (APTAC) aqueous solution (75 wt.%) were purchased from Sigma Aldrich (Saint-Quentin-Fallavier, France) and used as received.

Acrylic acid from the same suppliers was distilled under vacuum at room temperature. PEO Mn=5000 g.mol -1 , Ð = 1.04 was purchased from. 4,4'-azobiscyanopentanoic acid (ACPA, Aldrich, 98%) and 2,2-Azobis(isobutyramidine) dihydrochloride (AIBA, Sigma-Aldrich, 97%) were used as received.

For EC experiments, background electrolytes were prepared in ultra-pure water purified on a Millipore system (Molsheim, France) from tris(hydroxymethyl)aminomethane (TRIS, 99,9%, Merck), 4-Morpholinoethanesulphonic acid (MES, >99%, Acros Organics), and 2-[Bis(2-hydroxyethyl)amino]-2-(hydroxymethyl)propane-1,3-diol (BIS-TRIS, >99%, Acros Organics). Anisic acid (99,5%), ammediol (99,5%) used as markers for detection were purchased from Sigma-Aldrich.

Double-hydrophilic block copolymer synthesis

This section describes the synthesis of the copolymers. The synthetic pathway, the size exclusion chromatograms and the 1 H NMR spectra are given in SI as well as the temporal electropherograms.

Synthesis of poly(acrylamide)-b-poly(acrylic acid)

Aqueous RAFT/MADIX polymerization of AA

Polyacrylamide macro RAFT/MADIX agent (PAM-Xa, Mn= 5000 g.mol -1 ) was synthesized according the procedure described by Layrac et al.. [START_REF] Layrac | Hybrid Polyion Complex Micelles from Poly(Vinylphosphonic Acid)-Based Double Hydrophilic Block Copolymers and Divalent Transition Metal Ions[END_REF] Synthesis of PAM70-b-PAA20 was performed as follows [START_REF] Taton | Direct Synthesis of Double Hydrophilic Statistical Di-and Triblock Copolymers Comprised of Acrylamide and Acrylic Acid Units via the MADIX Process[END_REF] :

PAM-based chain transfer agent (PAM-Xa,) (15.76 g, 3.029 mmol), acrylic acid (4.24 g; 58.77 mmol), AIBA (0.0821 g, 0,3 mmol) and water (42 g) (solids = 30.6%) were introduced in a round bottom flask.

The mixture was degassed with argon at room temperature for 30 min and then placed in a thermostated oil bath at 65°C under argon for 2 hours. Conversion was quantitative, acrylic acid traces were eliminated by dialysis (MWCO 1000 Da) and pH-metric monitoring. The polymer solution was then freeze dried and a white powder was obtained. Four DHBC were synthesized according to this procedure: PAM70-b-PAA20, PAM140-b-PAA40, PAM140-b-PAA60 and PAM140-b-PAA80 (see Table 1).

Synthesis of poly(acrylamide)-b-poly((3-acrylamidopropyl)trimethylammonium chloride) Aqueous redox RAFT/MADIX polymerization of APTAC

Synthesis of PAM70-b-PAPTAC30 was performed as follows: two aqueous solutions of NaFS (5%w)

(1.23 g of solution, 0.4 mmol) and NaPS (5%w) (2.37 mg of solution, 0.5 mmol) were prepared. PAM-Xa macroxanthate (9.97 g, 1.99 mmol), APTAC monomer (13.3 g of solution, 0.057 mmol), and water (50 g) (solids = 25.4%) were introduced in a round bottom flask. The pH of the mixture was first adjusted at 2 with hydrochloric solution 1M. Then the mixture was degassed with argon at room temperature for 30 min and placed in a thermostated oil bath at 25°C under argon. Both solution of NaFS and NaPS were introduced in the round bottom flask and the reaction mixture was stirred for 3 hours. Monomer traces were eliminated with dialysis (MWCO 1000 Da) and conductivity monitoring. The polymer solution was then lyophilized and a white powder was obtained. This redox process at 25°C was developed after the paper of Sutton et al. [START_REF] Jacquin | Self-Assembly of Charged Amphiphilic Diblock Copolymers with Insoluble Blocks of Decreasing Hydrophobicity: From Kinetically Frozen Colloids to Macrosurfactants[END_REF] to minimize the formation of dead chains. Four DHBC were synthesized according to this procedure: PAM70-b-PAPTAC30, PAM70-b-PAPTAC60, PAM140-b-PAPTAC60 and PAM140-b-PAPTAC120 (see Table 1).

Synthesis of poly(ethylene oxide)-b-poly(acrylic acid)

Aqueous RAFT polymerization of AA Synthesis of PEO105-b-PAA20 was performed as follows: PEO105-CTA (poly(ethylene oxide)-chain transfer agent) macro RAFT agent was obtained following the procedure published by Bathfield et al [START_REF] Bathfield | Asymmetric Neutral, Cationic and Anionic PEO-Based Double-Hydrophilic Block Copolymers (DHBCs): Synthesis and Reversible Micellization Triggered by Temperature or pH[END_REF] .

PEO105-CTA, (10.53 g, 2.19 mmol), ACPA (0.123 mg, 0,439 mmol), acrylic acid (5.5 g, 76 mmol) and deionized water (29.5 mL) (solids=35.4%) were introduced in a Schlenk tube equipped with a magnetic stirrer. The mixture was degassed by five freeze-evacuate-thaw cycles and then heated for 42 hours at 75°C under nitrogen in a thermostated oil bath. Final conversion = 72%. Monomer conversion was determined by 1 H NMR spectroscopy, using a Bruker 400MHZ spectrometer. Samples for analysis by NMR were prepared by adding 0.6 mL of D2O to 0.1 mL of polymerization medium. Once the reaction was complete, the solvent was evaporated, and then the DHBC was dissolved in a minimum amount of dichloromethane before being precipitated twice in a large volume of cold diethyl ether. It was then recovered by filtration, and finally dried under vacuum overnight before analysis by SEC and 1 H-NMR.

SEC was performed in DMF-LiBr after methylation [START_REF] Kuhnel | Mechanism of Methyl Esterification of Carboxylic Acids by Trimethylsilyldiazomethane[END_REF] with trimethylsilyldiazomethane. Four DHBC were synthesized according to this procedure: PEO105-b-PAA20, PEO105-b-PAA30, PEO210-b-PAA40 and PEO210-b-PAA50 (see Table 1). The degrees of polymerization of the commercial starting PEO have been determined by [START_REF] Thevarajah | Quantifying the Heterogeneity of Chemical Structures in Complex Charged Polymers through the Dispersity of Their Distributions of Electrophoretic Mobilities or of Compositions[END_REF] H NMR [START_REF] Bathfield | Asymmetric Neutral, Cationic and Anionic PEO-Based Double-Hydrophilic Block Copolymers (DHBCs): Synthesis and Reversible Micellization Triggered by Temperature or pH[END_REF] and are presented in Table 1.

Synthesis of poly(acrylic acid)-b-poly(poly(ethylene glycol) methyl ether acrylate)

Aqueous RAFT polymerization of AA and PEGA 5,7-dithia-6-thio-4-methyl-4-cyanodecanoic acid (CTPPA) was obtained by reaction of ACPA with bis(propylsulfanylthiocarbonyl) disulfide according to literature. [START_REF] Boursier | Controlled Radical Polymerization of Styrene in Miniemulsion Mediated by PEO-based Trithiocarbonate Macromolecular RAFT Agents[END_REF] Synthesis of PAA21-b-P(PEGA)12 was performed as follows: PAA-CTPPA chain transfer agent was synthesized according to the process described in literature [START_REF] Chaduc | Effect of the pH on the RAFT Polymerization of Acrylic Acid in Water. Application to the Synthesis of Poly(acrylic acid)-Stabilized Polystyrene Particles by RAFT Emulsion Polymerization[END_REF] : in a round bottom flask, CTPPA (0.8 g, 2.57 mmol, purity=89%), acrylic acid (3.9g, 54.1 mmol), ACPA (0,072 g, 0.26 mmol) and half of the amount of water (7.5 g) are stirred until dissolution of CTPPA. The remaining water (7.5 g) was introduced and the mixture was degassed with argon for 40 min. The mixture was then heated in an oil bath at 70°C for 5.5 h. For the synthesis of PAA-b-P(PEGA), ACPA (0.0715 g; 0.26 mmol) and poly(ethylene glycol) methyl ether acrylate (12.8 g, 26.4 mmol) were added to the PAA-CTPPA reaction medium and the mixture was degassed with argon for 40 min. The mixture was then heated in an oil bath at 70°C for 5 h. Conversion was followed by [START_REF] Thevarajah | Quantifying the Heterogeneity of Chemical Structures in Complex Charged Polymers through the Dispersity of Their Distributions of Electrophoretic Mobilities or of Compositions[END_REF] H NMR. At the end of the polymerization, water was evaporated under reduced pressure and the polymer washed with diethyl ether. NMR sample preparation: 0.6 mL of D2O was added to 0.1 mL of polymerization medium and quenched in liquid nitrogen. Two DHBC were synthesized according to this procedure: P(PEGA)12-b-PAA21 and P(PEGA)22-b-PAA45 (see Table 1).

Capillary electrophoresis

Instrumentation and method

Capillary electrophoresis experiments were performed on an Agilent 7100 capillary electrophoresis instrument with a diode array UV detector. Fused silica capillaries of 50/375 µm I.D./O.D. with polyimide outer coating (cat. no. TSP050375) were from Polymicro Technologies (Phoenix, AZ, USA).

Capillary dimensions were 38.5 cm long (30 cm to detection window). New capillaries were conditioned by performing the following washes at 1 bar: 1M NaOH for 30 min and water for 15 min. The temperature of the capillary cartridge was set at 25 °C.

In the case of PAM-b-PAA, an electrolyte consisting of 20 mM MES and 14 mM ammediol pH 6.5 was used. 0.1 g/L anisic acid was added in the sample as a mobility marker. The same background electrolyte was used for PAM-b-PAPTAC, but with a different mobility marker (imidazole 0.1 g/L). In the case of PEO-b-PAA and P(PEGA)-b-PAA, an electrolyte constituted of 6 mM anisic acid and 12 mM BIS-TRIS, pH 6.5 was used as buffer, with MES at 0.5 g/L as mobility marker in the case of P(PEGA)-b-PAA.

All copolymers were dissolved in water at a concentration of 5 g/L. Samples were injected hydrodynamically on the inlet side of the capillary by applying 30 mbar for 5 s.

Electropherogram data treatment

Scale transformations. In this section, the transformations of the electropherograms into distributions of the parameter of interest are described following a previously published protocol [START_REF] Chamieh | Quantitative Analysis in Capillary Electrophoresis: Transformation of Raw Electropherograms Into Continuous Distributions[END_REF] . Briefly, experimental raw time-scale electropherograms, were first corrected from any baseline shift using

Origin (Origin 2016, OriginLab, USA) as depicted in step 1, Figure 2. For quantitative purpose, the absorbance signal S(t) was next divided by the migration time (t) to correct the differences in analyte

ep eo lL µ V t t  ( 5
)
where l is the effective capillary length, L is the total capillary length, t is the migration time, teo is the EOF marker migration time and V is the separation voltage.

Moments of the electrophoretic mobility distribution

The average effective mobility of the diblock copolymer diblock ep µ was obtained by integration of the peak of the copolymer in the effective mobility scale according to:

, , , 1 , , , 1 , ( ) ( ) () () ( )(
)

ep i ep i ep i ep i ep ep ep diblock i ep ep ep ep i ep i ep i i P µ µ µ µ P µ µ dµ µ P µ dµ P µ µ µ          (6)
where integration is carried out over the peak. In practice the integration is done numerically and the i index represents the digitized experimental data points. The summation is carried out over values of 𝑃(𝜇 𝑒𝑝,𝑖 ) greater than the median of the base line added to its standard deviation. Calculation of diblock ep µ was performed using Excel 2016 (Microsoft, USA), following the discrete form of equation (6).

Variance of the diblock electrophoretic mobility was obtained by the following equation:

  2 2 , , , 1 , 2 , , 1 , ( )( ) ( ) ()
           (7)

Results and discussion

Electrophoretic separation of the DHBC

The main goal of the CE characterization is to provide information about the chemical composition 2) is significantly closer to zero than that of P(PEGA)-b-PAA copolymers ( diblock ep µ ranging from -36 to-38 TU, Table 2), although the molar masses are close. This is because P(PEGA), a comb-like polymer, is more compact than linear PEO of the same molar mass. As a consequence, the drag force due to the neutral block is lower for P(PEGA) than for PEO.

As for PAM-b-PAPTAC copolymer, PAPTAC homopolymer was detected at about +43TU, as a shoulder merged in the copolymer distribution, only for the DPneutral/DP0 equal to 140/100 and 70/57 samples. Figure 3D 3). Besides, the 2-phenylacetate ester of PEO is a better homolytic leaving group than PAM. [START_REF] Moad | Living Radical Polymerization by the RAFT Process ? A Third Update[END_REF] Furthermore, the synthesis of PAM-b-PAA cumulates two successive RAFT/MADIX polymerizations of AM and AA, whereas the synthesis of PEO-b-PAA starts from a narrow PEO-CTA (Ð = 1.04) (PEO obtained by anionic polymerization) to perform a single RAFT polymerization of AA. This is consistent with the higher dispersity of PAM-b-PAA compared to PEO-b-PAA [START_REF] Taton | Direct Synthesis of Double Hydrophilic Statistical Di-and Triblock Copolymers Comprised of Acrylamide and Acrylic Acid Units via the MADIX Process[END_REF] . In addition, in reversible-deactivation radical polymerization [START_REF] Jenkins | Terminology for Reversible-Deactivation Radical Polymerization Previously Called "Controlled" Radical or "Living" Radical Polymerization (IUPAC Recommendations[END_REF] , at full conversion, the dispersity as defined by the ratio of the weight average molar mass over the number average molar mass, decreases when the DP increases [START_REF] Harrisson | The Downside of Dispersity: Why the Standard Deviation is a Better Measure of Dispersion in Precision Polymerization[END_REF] :

11 1 ex Ð DP C    ( 8
)
where DP is the targeted polymerization degree and Cex is the degenerative chain transfer constant between dormant and active chains [START_REF] Goto | Kinetics of Living Radical Polymerization[END_REF][START_REF] Molina | Drug-Polymer Electrostatic Complexes as New Structuring Agents for the Formation of Drug-Loaded Ordered Mesoporous Silica[END_REF] , which is consistent with a higher dispersity for a shorter poly(acrylic acid) block in PEO-b-PAA.

To get a better description of the copolymer distribution, it would be interesting to get a distribution of a new parameter which is directly related to the chemical composition of the copolymer instead of the electrophoretic mobility, which is not linearly dependent on the copolymer composition. This is the purpose of the two following sections.

DPneutral

Change of variable from µep to the retardation parameter Xexp

The drag effect of the neutral block can be expressed by the retardation parameter Xexp defined as : where b1 is the neutral monomer size. The Kuhn statistical segment length (which is twice the persistence length) is a measure of the polymer stiffness. Parameter 1 in Equation (10b) is a relative friction coefficient and it is non-dimensional. Since the polyelectrolyte is generally stiffer than the neutral block, 1 is often much smaller than unity [START_REF] Nedelcu | Branched Polymeric Labels Used as Drag-Tags in Free-Solution Electrophoresis of ssDNA[END_REF] .

00 exp 1 diblock ep ep ep diblock diblock ep ep µ µ µ X µµ     (9)
As for model 2, it is clear from equation ( 2) that the X parameter is directly expressed as the ratio of the hydrodynamic radius of each block:

mod ,2 0 neutral h el h R X R  (11a)
which can be rewritten as a function of the degrees of polymerization of each block by:

1 0 1 mod ,2 00
a neutral el a C DP X C DP  (11b)
where C1 (resp. C2) and a1 (resp. a2) are, respectively, the prefactors and exponents for the neutral (resp. charged) block in the relationship between Rh and DP. Note that a0 and a1 are supposed to be close to 0.5-0.6 for coil conformations, and slightly higher for more extended conformations.

As for model 3 (see equation ( 3)), the X parameter is directly expressed as:

  1/3 3 10 h A M R N         
, where [] is the intrinsic viscosity and Na is the Avogadro number. from ref [START_REF] Cranford | Variation of Weak Polyelectrolyte Persistence Length through an Electrostatic Contour Length[END_REF] (see Table 1 and Figure 13(a) herein).

The results are consistent with model 1 which predicts a linear dependence of the retardation parameter distributions. As for models 2 and 3, they lead to poor correlations between theoretical model,i X versus experimental exp X values (see Figure 6).

The knowledge of 1 provides the last relation necessary to carry on the general scheme presented in Figure 2 to its end and which leads to the distribution of ratio of chemical composition. In practice, we used1,exp obtained in Figure 5 together with equation (10b) to transform the data of Figures 4A to 4D

into the distributions presented in Figures 7A to 7D, using the following equation: given in Table 3. Experimental conditions as in Figure 3. was obtained using eq. ( 14). In (C), the MES peak has been removed. In (A), the sharp peak is a mobility marker (anisic acid) and was deleted before peak integration.

1 0 0 () () neutral neutral DP PX P P X DP DP DP X                  (

Conclusion

In an effort to make information provided by capillary electrophoresis more directly useful for polymer chemists, a protocol was proposed to convert electrophoretic mobility distributions of double hydrophilic block copolymers into distributions of chemical composition ratios. This ratio of composition is expressed as the ratio of the degrees of polymerization of each block Finally, the transformation of electrophoretic mobility distributions into composition ratio distributions significantly improved the comparison of the distributions between the different copolymer families, since it takes into account the differences in expansion and drag force according to the chemical nature of the blocks.

Supporting Information.

Synthetic pathway, SEC and NMR characterizations, raw electropherograms are provided for all dibloc copolymers studied in this work.

  DHBCs, namely, poly(acrylamide)-block-poly(acrylic acid) (PAM-b-PAA), poly(acrylamide)-blockpoly((3-acrylamidopropyl)trimethylammonium chloride) (PAM-b-PAPTAC), poly(ethylene oxide)block-poly(acrylic acid) (PEO-b-PAA) and poly(poly(ethylene glycol) methyl ether acrylate)-blockpoly(acrylic acid) (P(PEGA)-b-PAA). These DHBC have been synthesized in aqueous medium by reversible addition-fragmentation transfer (RAFT) polymerization.

  work. The subscripts in the names correspond to the degree of polymerization of each block. MWneutral and MW0 are the molar masses of the neutral and of the polyelectrolyte block respectively. Type of DHBC MWneutral-MW0 as determined by NMR Chemical structure PAM70-b-PAA20 5k-1.4k PAM140-b-PAA40 10k-2.8k

  Separations were carried out by applying a +20 kV voltage. For PAM-b-PAA, PEO-b-PAA and P(PEGA)-b-PAA and PAM-b-PAPTAC, detection was realized at 192 +/-2 nm (reference off). For PAM-b-PAA, PEO-b-PAA and P(PEGA)-b-PAA, the capillary was rinsed between each run by flushing the capillary for 2 min with the background electrolyte, 2 min with 0.1 M NaOH, 2 min with ultra-pure water and 2 min with background electrolyte. For the analysis of the cationic polymer PAMb-PAPTAC, and in order to reduce the adsorption on the capillary wall, surface of the capillary was modified using UltraTrol™ LN (Target Discovery, Inc., Palo Alto, CA), which is a commercial neutral semi-permanent coating based on polyacrylamide derivatives. The coating procedure was performed using the following successive flushes: methanol for 2 min at 1 bar, water for 2 min at 3 bar, 1 M NaOH for 2 min at 3 bar, 0.1 M NaOH for 2 min at 1 bar, 1 M HCl for 5 min at 1 bar, water for 5 min at 1 bar, UltraTrol™ LN solution for 5 min at 1 bar, wait for 5 min, water for 2 min at 1 bar. Prior to each analysis of PAM-b-PAPTAC, the capillary was rinsed with the background electrolyte for 2 min at 1 bar.

Figure 2 ..

 2 Figure 2. General scheme for changing a time-scale electropherogram into a mobility-scale and Xexp-scale distributions. The raw electropherogram is first corrected from baseline shift (1). The time-scale electropherogram is then corrected from the differences in analyte velocities (2). The time-corrected electropherogram is converted into the effective mobility-scale distribution (3). The mobility-scale

Figure 3 .:

 3 Figure 3.: Distributions of effective electrophoretic mobility obtained for PAM-b-PAA (A), PEO-b-

6 .

 6 displays DEM ranged between +22 and +41 TU, with higher effective mobilities for the DHBC of highest charge. Comparison of PAM-b-PAA series with PAM-b-PAPTAC series illustrates the importance of the nature of the blocks on the drag effect of the neutral block. This effect is discussed in more detail in section 4.2.As a general trend, electrophoretic mobilities of DHBC are always closer to zero than those of the homopolyelectrolyte which are: PAA= -42 TU; PAPTAC= +44 TU, and the electrophoretic mobility of the DHBC increases as the proportion of charged monomers in the DHBC increases (see FigureSI 20).In terms of EM dispersion, the least dispersed series is the P(PEGA)-b-PAA, with relative standard 5% to 9%, followed by the PEO-b-PAA ( the most disperse series is the PAM-b-PAA series with 20% to 30% relative standard deviation of the electrophoretic mobility. This dispersion in mobility results from both the level of control of the polymerization, and from the spatial extension of the polymer in the solvent. It can be explained by the chemistry of the RAFT polymerization (chain transfer agent R-SC(S)Z where Z is the activating group and R is the leaving group), for which the polymerization of acrylates is better controlled by dithiobenzoates (Z: -SC(S)Ph) (Ð < 1.2) than by ethyl xanthate (Z: -SC(S)OEt) (Ð > 1.

  integration, standard deviation of the electrophoretic mobility distribution µ, exp X value at peak maximum and average value exp X obtained by peak integration, standard deviation of the exp X distribution Xexp of all DHBC studied in this work. Note that the peak of anisic acid was first subtracted before integration for the calculation of diblock ep µ and µ  for PAM-b-PAA.

Figure 4 .

 4 Figure 4. Distribution of retardation parameter Xexp for PAM-b-PAA (A) PEO-b-PAA (B), P(PEGA)-

X

  Figure 5. Plot of

.Figure 5 ,

 5 Figure5, we can conclude that the linear correlation between exp X and

Figure 6 .

 6 Figure 6. Comparison between Xmodel,i and exp X

Figure 7 .

 7 Figure 7. Distribution of composition in terms of the ratio of the degrees of polymerization of both

.

  To get this composition ratio, we have introduced the retardation parameter X which takes into account the drag force exerted by the neutral block on the polyelectrolyte. The distribution of X that characterizes a DHBC is readily obtained from the experimental electropherogram and the relation between X and the ratio of DP. The latter is available from different models for electrophoretic mobility of composite objects. A linear relation has been found experimentally between the retardation parameter X and the ratio of DPs, within each of the four families of DHBC studied in this work. This result is consistent with the model of electrophoretic mobility of Long et al. that takes into account hydrodynamic coupling, although the prefactors are slightly overestimated. Our experimental findings not only support the theoretical prediction, but also facilitate the last step of data transformation, from distribution of X into distributions of ratios of DP.The dispersions in composition are in the order of: P(PEGA)-b-PAA < PEO-b-PAA ~ PAM-b-PAPTAC < PAM-b-PAA. Therefore, we can conclude that in the DHBC families, the PAM block leads to broader composition ratio distributions compared to a PEO block, when associated to a PAA block. Similarly, the P(PEGA) block lead to less disperse composition ratio distributions compared to a PEO block, when associated to a PAA block. Finally, PAA associated with PAM leads to broader composition ratio distributions compared to PAPTAC associated with PAM. The relatively low composition dispersity of the PEO-PAA block copolymer is most likely due to the low dispersity of the PEO block, prepared by anionic polymerization, and the use of a dithiobenzoate chain transfer agent, which has a higher chain transfer constant and thus gives narrower molar mass distributions than the xanthate chain transfer agent used to prepare the PAM-PAA and PAM-PAPTAC block copolymers. The use of a trithiocarbonate chain transfer agent and a relatively short P(PEGA) block leads to a fairly narrow composition distribution for P(PEGA)-PAA block copolymers.

  The polyelectrolyte block of the DHBC is composed of Nblob equivalent blobs of a size equivalent to the hydrodynamic radius of the neutral coil

				N	blob
		,1 diblock ep		0 blob   N i  i ep 1 		N	0 blob ep blob N     1 neutral ep		1	0 ep DP 0   	(1)
	where	i ep  is the effective mobility of the i th entity (or blob) constituting the DHBC,	0 DP is the degree
	of polymerization of the polyelectrolyte block, is the number of charged monomers per blob,	0  is
												ep
	the effective electrophoretic mobility of the polyelectrolyte part (alone) and		neutral	is the electrophoretic
												ep
	ep Figure 1. Representation of possible conformations of a double hydrophilic block copolymer composed of a mobility of the neutral part ( 0 neutral   ). The number of equivalent blobs in the polyelectrolyte chain
	neutral Gaussian coil (in red) linked to a polyelectrolyte block (in blue). In model 1, the polyelectrolyte chain
	is a coil in hydrodynamic interaction with the neutral Gaussian coil. In model 2, the polyelectrolyte and the is given by 0 blob DP N   diblock . Note that Nblob (and ep ,1 µ
	neutral polymer separate into two coils. In model 3, the polyelectrolyte is fully stretched and has no
	hydrodynamic coupling with the neutral coil. Adapted from 28
												R	neutral h	. If	R	neutral h	is larger or equal to the
	Debye length, Long et al. 29 demonstrated that the electrophoretic mobility of the DHBC composite
	object composed of Nblob +1 subunits of equal size, is given by the number-average of the electrophoretic
	mobilities calculated on all the equivalent blobs constituting the object. The electrophoretic mobility of
	the DHBC,	,1 diblock ep µ	, is thus given by 28 :

Table 1 :

 1 Presentation of the chemical structure and the different DHBC samples synthesized and studied in this

Table 2 .

 2 Electrophoretic mobility

					diblock ep µ
						diblock
			DP0	-	max peak	ep integration µ	(TU) µ 	X peak exp	integration exp X by		X	exp
						(TU)		max
					(TU)
			70-20		-22	-19.9	3.89	0.61	1.12	0.45
	PAM-b-PAA		140-40 140-60		-19.1 -23.3	-19.5 -21.4	5.44 6.19	0.74 0.58	1.26 1.05	0.73 1.0
			140-78		-25.3	-24.1	5.68	0.41	0.99	0.56
			105-20		-31	-30.2	4.83	0.28	0.33	0.12
	PEO-b-PAA		105-30 210-40		-33.8 -28	-33.2 -28.4	2.45 1.36	0.18 0.40	0.21 0.41	0.06 0.06
			210-50		-30.5		-30	1.97	0.30	0.34	0.64
	P(PEGA)-	b-PAA	21-11.5 44.9-22.2	-37.6 -37	-38.6 -36.6	3.61 2.41	0.059 0.079	0.043 0.098	0.09 0.08
			70-30		34.6		33.9	3.18	0.19	0.25	0.12
	PAM-b-PAPTAC		70-60 140-60 140-120	39.1 34.2 38.5		37.1 32 36.3	3.2 4.1 4.1	0.08 0.21 0.09	0.11 0.32 0.164	0.05 0.39 0.13
						µ	diblock	at peak maximum and average value
						ep

Table 3 .

 3 Characteristic parameters of neutral and charged blocks constituting the DHBC studied in this work. Mw

	are expressed in g/mol.

Acknowledgements

This work was supported by the MESOPIC project funded by the Agence Nationale de la Recherche (ANR) under grant # ANR-15-CE07-0005.

Finally, equations (10b) (11b) and (12b) demonstrates that, whatever the considered model, the X parameter is related to a compositional ratio between the neutral and the charged blocks with, however, different scaling dependences with the DP of each block, and with an additional logarithmic term in model 3. It is worth noting that in the case of hydrodynamic coupling (model 1), the newly introduced variable varies linearly with the ratio of degree of polymerization of the two blocks.

The distributions of the Xexp parameter are simply deduced from the distribution of electrophoretic mobility using the following equation (Figure 2, step 4) [START_REF] Chamieh | Quantitative Analysis in Capillary Electrophoresis: Transformation of Raw Electropherograms Into Continuous Distributions[END_REF] :

All the Xexp distributions are presented in Figure 4. Since µep and Xexp are not linearly related, the change of the variable from µep to Xexp modify the form of the distribution. The different moments characterizing the distribution of Xexp are calculated using similar relations as equations ( 6) and ( 7) and are reported in Table 2.

Xexp


Yvonne-Anne Pignolet

Stefan Schmid

Gilles Tredan

Implications of Routing Coherence and Consistency on Network Optimization

In network optimization problems, from traffic engineering to network monitoring, the routing model is typically considered as something given and fixed. This paper is motivated by the fundamental question how the ability to change and optimize the routing model itself influences the efficiency at which communication networks can be operated. To this end, we identify two main dimensions of the routing model: consistency (of a single route) and coherence (of sets of routes). We present analytical results on the impact of the routing model on the achievable route diversity as well as on the runtime of solving optimization problems underlying different case studies. We also uncover that it can sometimes be beneficial to artificially restrict the routing model, to significantly reduce the computational complexity without negatively affecting the route diversity much.

I. INTRODUCTION

While most communication networks feature a routing mechanism which supports the delivery of packets from their source s to their destination t across a multi-hop network, they can differ significantly in how and to what extent the routes taken by packets can be controlled. Routing models have evolved dramatically over the last years, and indeed, more flexible routing models have been a main driver behind recent innovations in networking [START_REF] Feamster | The road to sdn: an intellectual history of programmable networks[END_REF]. At one end of the spectrum lie traditional networks in which packets are routed along shortest paths and in a (IP prefix) destination-based manner (using protocols such as, e.g., OSPF). Such networks often provide only limited flexibility: destination-based routes are confluent, and flows towards the same destination remain on the same route once they meet. Furthermore, the only knob available to the operator to influence the routes is to set the link weights based on which the shortest paths are selected. In the late 1990s, increasing traffic volumes and the need for a more reliable performance led to the design of more advanced routing technologies (traffic engineering). MPLS enabled a per-flow traffic engineering, supporting the definition of more general (not necessarily shortest) routes, and SDNs and OpenFlow facilitated a direct control over the forwarding tables. In particular, besides forwarding, SDN and OpenFlow also support a more general modification of packet headers, enabling more advanced routing services: packets may are not only forwarded along simple paths, but routes may have loops.

But not only the technology and specific protocols can influence the flexibility at which routes can be selected, but also the network policy. For example, inter-domain routes in the Internet are often driven by business/financial aspects and may be valley-free. There also exist policies which force traffic to be routed via certain waypoints (e.g., a middlebox for deep packet inspection, a firewall, or a WAN optimizer) between source and destination [START_REF] Kloti | Policy-compliant path diversity and bisection bandwidth[END_REF], or to explicitly avoid such waypoints (e.g., routing via certain countries or via certain network elements such as route reflectors). Thus the routes taken by packets can depend on aspects beyond the pure network topology.

This paper is motivated by the observation that while it is intuitively clear that different routing models have an impact, we lack a systematic comparison of existing and future routing models, not only with respect to the routing flexibility they provide (the "route diversity"), but also with respect to the cost resp. quality and time complexity at which network optimization problems can be solved in these different routing models. Indeed, as we show in this paper, and complementing the perspective usually taken in the literature, many aspects of network optimization to a large extent does not only depend on the complexity of underlying network topology but also on the routing model used.

Our main contributions are a systematic study of the impact of the routing model on fundamental network optimization problems. To this end, we first propose a taxonomy of routing models, along two dimensions, consistency and coherence:

1) Consistency (⇧): Consistency relates to properties of a single route, e.g., some routing models require shortest or loop-free paths, or policies may dictate that packets should (not) go through a certain waypoint. 2) Coherence (⌃): Coherence refers to constraints on how multiple routes relate to each other. For example, packets must travel confluent routes towards the same destination.

We illustrate how the consistency and coherence influence the diversity of routes on a given network and propose a hierarchy of coherence models which impacts the achievable performance. Furthermore, we demonstrate how routing algebra properties can impact coherence. We consider two canonical problems as case studies. (i) Traffic Engineering: A main goal of Traffic Engineering is to keep load low, thus we consider the impact of routes on network load in this case study. (ii) Monitoring: Dependable communication networks require (automated) monitoring, e.g., to check the availability of links or entire routes. The objective in this case is hence to keep track of the network state at low cost. Moreover, we show how routing models can help to prove new properties using OSPF as an example.

ISBN 978-3-903176-28-7 c 2020 IFIP Our approach leads to several interesting observations. For example, we find that the same optimization problem on the same network can be polynomial-time solvable under one routing model and NP-complete under another routing model. This uncovers an optimization opportunity: by restricting the routing model artificially, i.e., by introducing constraints on the routing which do not negatively affect the route diversity by much, the computational complexity may be reduced significantly.

II. A TAXONOMY OF ROUTING MODELS

This section first introduce a basic network model and then presents and discusses a taxonomy to classify routing protocols.

A. Preliminaries

We consider a basic model in which the network is represented as an undirected connected graph G(V, E), with n = |V | devices (nodes) and m = |E| communication links connecting them. Nodes and links may have attributes representing costs, constraints, etc assigned to them. An (s, t)-

route is a sequence of k nodes r = (v 1 = s, v 2 , . . . , v k = t) such that (v i , v i+1 ) 2 E.
Note that a route r does not necessarily have to follow a shortest path and not even a simple path: the route may contain loops (e.g., in order to visit a certain waypoint, such as a firewall, along the route), and hence, in graph theory terminology, the route forms a walk. However, for ease of presentation, we first focus on simple (but not shortest) paths, and write r[v i , v j ] to denote the subsequence of r between nodes v i and v j . Section II-E describes how to extend our model to routes with loops.

Given two routes r 1 , r 2 , we denote by r 1 \ r 2 the set of links appearing in both routes. Furthermore, we consider the graph induced by the union of two or more routes, ignoring the order of the links: thus r [ r 0 implies an induced network G(V, E), where

V = {v 1 , . . . , v k , v 0 1 , v 0 k 0 } and E = {(v i , v i+1 )|(v i , v i+1 ) 2 r _ (v i , v i+1 ) 2 r 0 }.
We refer to the set of all possible routes which differ by at least one edge between any two nodes x, y 2 V in G by R(x, y). In addition, we denote by R(x, .) (resp. R(., y)) the set of all routes that start at node x (resp. finish at node y). Finally, to emphasize when we consider all routes in a network G (not only between certain endpoints), we write R(G).

Given a set of source-destination pairs, a routing algorithm produces a set of routes for these pairs. In this paper we do not focus on the algorithms constructing these routes but rather on the properties the resulting route sets exhibit: Hence the routing algorithms are abstract providers of routes. This allows us to first compare all algorithms on a generic basis, and second to classify algorithms using properties on their route sets that are useful from a theoretical and practical perspective.

Definition 1 (Route Set S). A route set S ⇢ R(G) contains zero, one or several routes r i 2 R(G) for each sourcedestination pair.

Consistent with this approach, when we study properties of routing models, we will distinguish between blackbox properties which can be checked by only observing the routes themselves, as opposed to whitebox properties that require additional knowledge on the "infrastructure", e.g., on the network topology, link weights, algorithm parameters, etc.

B. Dimension 1: Consistency

The first dimension of our taxonomy is consistency: a property defined on individual route of a route set. Formally, a route r on a graph G is ⇧-consistent if the predicate ⇧(r, G) defined over the links and nodes of the route r on G evaluates to true. For example, a basic consistency predicate is that all routes of a route set are of minimum length: shortest path routing is employed by well-known protocols, e.g., OSPF, which ensure that all flows are routed along shortest paths with respect to edge lengths (routing weights). Other examples of consistency properties are related to the policy-compliance of a given flow, e.g., ensuring that a route did traverse certain waypoints, did not traverse blacklisted parts of the network, or conforms to business relationships (like valley-freedom).

In general, a consistency predicate ⇧ can be used as a filter: only a subset of all possible routes R(x, y) between x and y may fulfill ⇧. In the following, let R ⇧ (x, y) ⇢ R(x, y) denote the set of routes from x to y that are consistent w.r.t. ⇧. We write R ⇧ (G) and call it the set of all ⇧-consistent routes of a graph G.

Note that many of the consistency predicates used in practice depend on properties of the elements of the underlying network infrastructure, such as waypoints, edge type classes or weights representing the cost or latency incurred when using them. In particular, predicates such as "is a shortest path" even require additional information about the infrastructure, beyond the links of the current path: in order to be able to verify that this path is indeed the shortest between a given source and a given destination, we need to know the alternative links (and their weights) in G. However, there are also consistency properties which do not require such additional information, for example a predicate of the form "the route length is at most `" or loopfreedom. We will refer to consistency properties which depend on the infrastructure as whitebox consistency properties, and to consistency properties which do not require such information, as blackbox consistency properties.

Consistency properties (e.g., valley-freedom, waypoint routing, multipathing, etc.) are often described using regular languages [START_REF] Soulé | Managing the network with merlin[END_REF], [START_REF] Kloti | Policy-compliant path diversity and bisection bandwidth[END_REF], [START_REF] Jensen | P-rex: Fast verification of mpls networks with multiple link failures[END_REF], e.g., over labels on links and nodes: it is required that all valid routes in the graph adhere to this regular expression. For example, s. ⇤ w. ⇤ t could express that a route from s to t should traverse a waypoint w. Or (c2p) ⇤ (p2p)?(p2c) ⇤ could express a valley-free routing policy where edge labels are used to denote peer-to-peer (p2p), provider-to-customer (p2c), or customer-to-provider (c2p) relationships [START_REF] Kloti | Policy-compliant path diversity and bisection bandwidth[END_REF].

Another approach, based on algebraic methods, considers routing policies as a function that selects, from the set of all paths from a source to a destination, preferred paths according to predefined rules. Simply put, a routing algebra defines a set of "legal" or policy-compliant routes. This definition is broad enough to contain many routing policies, e.g., shortest paths, widest path, most reliable path, widest-shortest path, shortestwidest path, valley-free paths, etc. A large body of literature analysed routing protocols in such a framework, e.g., [START_REF] Sobrinho | Network routing with path vector protocols: Theory and applications[END_REF], [START_REF] Rétvári | Compact policy routing[END_REF], [START_REF] Gurney | Lexicographic products in metarouting[END_REF], [START_REF]Netkat: Semantic foundations for networks[END_REF] to name but a few.

The crucial components of a routing algebra are a partiallyordered commutative semi-group with a compatible infinity element: A = (W, , L , ), where W is the set of possible edge weights (i.e., different edges can have different costs), ( / 2 W ) denotes an infinity element assigned to unusable edges/routes, and L is a composition operator for weights (e.g., latency related edge costs add up while bandwidth-related edge costs are naturally subject to min/max operations). Given a route we obtain its weight by combining the weights of its constituent edges with L . is a partial order for weight comparison of edges and routes. A preferred route in the algebra A between two nodes is one with the smallest weight according to . The infinity weight is compatible with (W, L ) according to in the sense that it is absorptive w L = , 8w 2 W (a route with contains an unusable edge is unusable), and maximal w , 8w 2 W (any route without an unusable edge is preferred over a route with an unusable edge).

To give an example, shortest path routing, where valid paths between two nodes minimise the sum of the weights of its constituent edges, corresponds to the algebra (R+, 1, +, ), where positive edge weights (R+) may describe a property like the latency or cost of this edge, which is added up (+) along a route, and shorter routes are better (). Widest-path routing prefers paths which have the largest bottleneck capacity, i.e., (R+, 0, min, ) where positive edge weights (R+) describe the link bandwidth, the total bandwidth provided along a route is the minimum (min) offered on any of its constituent links, and wider paths are better ( ).

C. Dimension 2: Coherence

The second dimension concerns the coherence ⌃(R, G) of route sets R produced by a routing algorithm. Similarly to the above, we denote by R ⌃ the set of route sets that fulfill a coherence predicate ⌃. Since ⌃ describes a relationship between multiple routes, R ⌃ is a set of sets: each set of routes R 2 R ⌃ satisfies the coherence predicate ⌃.

Note that a coherence predicate compares multiple routes to each other (e.g., if and in which nodes and links they are the same or different). Many important coherence properties do not require references to the infrastructure network G (i.e., they are blackbox coherence properties). Take for example destination-based routing, which can be expressed generally as "once two routes towards the same destination meet, they will follow the same route from then onward". Indeed, as we will see, when describing coherence properties, it often matters when two routes meet.

There are also whitebox coherence properties, which require knowledge about the infrastructure. For example, consider a network which includes two waypoints w 1 , w 2 of the same type (e.g., an intrusion detection system). A coherence property may require that two flows, one from s 1 to t 1 and one from s 2 to t 2 , either both go through w 1 or both go through w 2 . Some natural coherence properties are the following:

Definition 2 (Basic Coherence Property Examples).
Let G be a graph and ⌃ a coherence predicate. Basic coherence properties include:

(i) Multi (?): In this model, an arbitrary subset of R(G) is valid: for each set of routes R 2 R ⇤ , it holds that R ✓ R(G).
In particular, more than one route between a source and destination node may be included in R.

(ii) Any (!): In this model, we only require that at most one route between any source-destination pair exists, and there are no other constraints on the route: for each set of routes

R 2 R ! , it holds that |R(x, y)|  1 8x, y 2 V (G). (iii) Confluent (>):
In the confluent model, the route choice at each node is source-invariant. I.e., the next hop is determined by the destination.

Let R 2 R > (G) 8w, y 2 V, 8r, r 0 2 (R \ R(., y)) it holds that w 2 r \ r 0 ) r[w, y] = r 0 [w, y].
Note that such an element w 2 r 0 \ r has to carry the same inport and attribute in both sequences. This also holds for all elements in r[w, y] and r 0 [w, y].

(iv) Contained (✓): In the contained model, any two routes share at most one contiguous subsequence 8z, w 2 V, 8r,

r 0 2 R it holds that {z, w} 2 r \ r 0 ) r[z, w] = r 0 [z, w]. (v) Forest (T )

and Graph (G ):

In the most constrained model, the union of all routes in any set R 2 R T is a forest. More generally, the coherence restriction could be extended R 2 R G for other graph classes, e.g., DAGs or planar graphs.

(vi) Symmetric Routing ($): A set of routes R is symmetric if it holds for all source-destination pairs (s, t), if a route r from s to t is in R then the reverse route from t to s is in R too.

Note that these coherence properties differ in terms of the path subsequences shared by the different routes. E.g., ? and ! do not have any constraints on shared subsequences, while >, ✓, T, $ require shared subsequences to adhere to rules. In symmetric routing, the same routes between two nodes are used in both directions. It is easy to see that for example routes adhering to T routing models are always symmetric. For an example where the confluent > and the contained ✓ routing models are different, see Figure 1 with valid confluent routes which are not contained.

D. Combining Consistency and Coherence

There can hence be two different types of restrictions on a route set: related to consistency ⇧ and related to coherence Given a message m from s to t (code for node v)

1: C = arg min i2V (v) (d(i, t)) /
/⇤ algorithm continues ⇤/ argmin i2C (i) argmin i2C (|i s|) random(i 2 C) s 1 s 2 v t u1 u2 s 1 s 2 v t u1 u2 s 1 s 2 v t u1 u2
Fig. 2. Prototype of a shortest path routing algorithm, and impact of the tiebreaking. Produced routes are always consistent. Depending on the nature of the tie breaking, the set of produced routes will have different properties. In the blue example, routes will always be confluent, whereas in the green examples, the produced route set might be Any (!). A non-deterministic tie-breaking like in red may produce Multi (?).

⌃. Both limit the classes of route sets R ⌃ ⇧ (G) through a given network G. For any set of routes R 2 R ⌃ ⇧ (G), the routes R jointly fulfill ⌃, and each route individually fulfills ⇧. For many networking problems R ⌃ ⇧ (G) serves as a better class definition when reasoning about network algorithms (e.g., for traffic engineering, monitoring, etc.) than the network topology or consistency and coherence properties individually (as discussed in more details later). Motivated by our observations, we will define a route set to adhere to a routing model as follows.

Definition 3 (Routing Model M). Let ⇧ be a consistency criterion and ⌃ a coherence criterion. The routing model M ⌃ ⇧ (G) consists of all route sets S that satisfy ⇧ and ⌃, i.e., S ⇢ R ⇧ and S 2 R ⌃ .

The fewer constraints we have on coherence and consistency for a routing model, the higher the number of schemes satisfying the predicates. In other words, less constrained models M ⌃ ⇧ contain route sets of larger size and more route sets.

In Figure 2 we illustrate the connection between a routing algorithm and the resulting routing model. It presents a partial prototype of a shortest path routing algorithm: line 1 ensures that paths are selected according to this consistency criteria. However, depending on the contents of line 3, the resulting routing model might end up having various coherence properties. Below, we depict the consequences of 3 example implementations, together with the possible resulting routes.

This example demonstrates the importance and impact of tie-breaking in such protocols. Other protocols may not fit this prototype algorithm, yet produce route sets that obey the Routing Algorithm same logic. Let us also underline that many routes are affected by line 3, for instance in a regular hypercube there are 2 k 1 shortest paths to nodes at distance k: the actual route will be selected through k 1 successive evaluations of line 3.

route a!b route b!c route c!b ...

Route

E. Generalization for Routes with Loops

Our definitions can easily be extended beyond simple paths. In this case, we do not only have to account for the current node and destination, but also have to consider the packet's state, e.g., a flag denoting whether a packet is on its route "before or after the waypoint", as well as the router's state (e.g., counters). These states can be modelled as additional attributes, which can be matched in forwarding rules of routing protocols. Analogously, the resulting routes can be annotated with these attributes. Thus the notion of two routes "meeting" at a node v in our taxonomy needs to be generalised to refer to these annotations. I.e., two routes meet if in addition to visiting the same node they feature the same attributes at this node. Another way of looking at this, is to consider a node v occurring on routes with attributes a 1 and a 2 as two different instances of a node, v 1 and v 2 respectively. On the multi graph induced by the set of annotated nodes and links the routes are thus loop-free and the original definitions can be used.

F. Summary and Taxonomy

In summary, we propose to study sets of routes as the generic consequence of any routing algorithm. This allows us to focus only on the consequences of these algorithms in our taxonomy (Figure 3), regardless of the internal logic that led a given algorithm to produce a particular set of routes.

Inside this model, we identify two canonical categories of properties to describe those route sets: (i) consistency properties, describing properties satisfied by each individual route of the considered set (e.g., properties that paths are simple, shortest, or at most k hops long). And (ii) coherence properties, describing properties satisfied by the route set as a hole (e.g. the routes are symmetric, confluent). We can further distinguish two types of coherence properties. First, internal coherence properties, that can be expressed using only elements of the route set (e.g., the route set is contained) and can be seen as the counterpart of consistency (expressed as predicates involving a single route against elements of the infrastructure). Second, generalized coherence properties, that can only be expressed using predicates involving both multiple routes and elements of the infrastructure. We can then define the routing model as the combination of consistency and coherence properties fulfilled by a route set. We illustrate in Figure 2 how a simple shortest path routing algorithm (designed with a predefined consistency criteria) can provide route sets belonging to different routing models because of the different coherence properties induced by its tie-breaking behavior.

III. GENERAL ANALYSIS AND IMPLICATIONS

This section presents an analysis of the impact of the routing model, based on our taxonomy, namely route diversity, hierarchies and the interdepence of routing algebra properties and coherence.

A. Notions of Route Diversity

Given our taxonomy, we can refine the intuitive notion of "path diversity". First, the term route diversity is more accurate to represent the flexibility offered by a variety of routes between a source and destination since routes do not necessarily have to follow simple paths and may contain loops, as discussed earlier. Route diversity can come in different flavors.

If we consider consistency only, we can define (s, t) ⇧ -routediversity to count the number of different ⇧-consistent routes a packet travelling from source s can take to reach its destination t on a graph G. E.g., there might be several shortest paths between s and t, or several valley-free paths. The higher this number, the more distinct ⇧-consistent route sets exist.

For a given route set R, we can define the (s, t)-routeset-diversity to be |R(s, t)|, the number of distinct routes between s and t in R. We further define (s, t)-subsequenceroute-set-diversity as the number of different routes a packet travelling through s and t can take, according to a route set R (regardless of the source and destination of packets), i.e.,

|{r|r 2 R ^len(r[s, t]|) > 0}|.
Note that the subsequence-route-set-diversity definition is more general in the sense that depending on a routing model certain paths between s and t may only be traversed by packets emitted by s 0 and not by packets originating at s. To indicate the complexity and quality of some problems one of the two may be more appropriate. E.g., for the monitoring problem described in our case study (see Section IV) the subsequenceroute-diversity of a routing model matters. This is due to the fact that a route measurements can be used to infer metrics of the links they contain and thus a r[u, v] subsequence of a (s, t)route r traversing u and v can monitor links in r[u, v], even though there might be no (u, v)-route that contains r[u, v].

To analyze the impact of ⇧-consistency and ⌃-coherence not just on a pair of nodes and of single route set but on the number of route sets that conform with ⇧ and ⌃ , we can define the routing model diversity as diversity ⌃ ⇧ := |M ⌃ ⇧ |, the number of route sets that adhere to M ⌃ ⇧ . To illustrate how the routing model affects route diversity, let us consider a fundamental example, depicted in Figure 4. Let S be the set of route sets with routes between a set of s sources s 1 , . . . s s and two destinations t 1 and t 2 . In this example, the blue nodes connect sources and destinations by k parallel routes of the same length. The number of possible loop-free !coherent route sets is thus

diversity ! ↵ = k s+2 , diversity > ↵ = diversity ✓ ↵ = k 2
for the confluent and contained routing model and diversity T ↵ = k for forest-coherent routing. The first observation drawn from these results concerns the restricting power of routing models. While the network exhibits a number of loop-free route sets growing exponentially with the number of sources in the ! model, this combinatorial explosion is no longer possible under more restrictive routing models. The impact of the topology on those restrictions can be seen very well on outerplanar graphs: the number of tree route sets is still exponential in the number of faces (which in turn can be as large as ⌦(n)).

Similarly to the coherence example above, consistency influences the route model diversity. Consider two nodes s, t on an odd cycle. Under shortest path consistency there is exactly one route between s and t possible and thus every !-coherent route set is also >-coherent. A more relaxed consistency criteria may allow two routes. In this case, we could construct an !coherent route set that is not confluent by adding the long routes for the two neighbors of t.

B. Coherence Hierarchy

We first observe that some of the properties defined in the previous section form a hierarchy of increasingly flexible routing. In particular the number of possible route sets R ⌃ ⇧ (x, y) between two nodes x and y (or on G in general), depends, besides the topology, on the routing model defined by ⌃ and ⇧.

In the following, we prove the hierarchy of coherence (for any consistency property ⇧ as it affects all sets the same way).

Theorem 1. Let G be a graph. We have R T ⇧ (G) ✓ R ✓ ⇧ (G) ✓ R > ⇧ (G) ✓ R ! ⇧ (G) ✓ R ? ⇧ (G), for any consistency ⇧.
Proof. To improve readability, we omit the subscript ⇧ in the proof. Only routes that satisfy ⇧ are considered in the following. Containment: Let S 2 R T (G) be the union of all routes, forming a tree. In particular all routes that pass through a particular node w form a tree and thus at most one contiguous subsequence for each pair of routes, hence S 2 R ✓ (G).

Let S 2 R ✓ (G) and let w be a node. All pairs of routes containing w have at most one contiguous subsequence. This holds in particular for routes destined for w: S 2 R < (G).

Let S 2 R < (G). By contradiction assume that there exists x, y such that |R(x, y) \ S| > 1. Let r and r 0 two such routes. Since r and r 0 are in R(., y), we know that r [ r 0 do not split after they meet. Since x 2 r \ r 0 , we conclude that r[x, y] = r 0 [x, y] = r = r 0 .

We note that if the network is a tree, all models become the same (possible equality). We construct an example where all those coherence sets are equal. Let T be a tree, and ⌃ a classic "shortest path" consistency criteria. Observe that 8S 2 R ? (T ), S r2S r: we have R ? (T ) ✓ R T (T ), from which we conclude R ? (T ) = R T (T ), settling the case for the intermediary models !, < and ✓.

The tree example in the proof shows that topologies have an impact on the route diversity. More precisely, a greater link density allows for many routes, and hence allows for many route combinations that populate the routing models hierarchy.

Intuitively, a higher route diversity allows for more possible configurations, some of which may provide more desirable output. This intuition follows from Theorem 1.

Corollary 1. For any optimization problem, let qual(S, G) denote the quality measure of the best solution achievable on a graph G for a given route set S. G). This settles the case for R T ⇧ (G) and R ✓ ⇧ (G). The inequalities for the other cases can be derived analogously.

By ex- tension, let qual(R ⌃ ⇧ , G) = max S2R ⌃ ⇧ (qual(S, G)). Then qual(R T ⇧ (G), G)  qual(R ✓ ⇧ (G), G)  qual(R > ⇧ (G), G)  qual(R ! ⇧ (G), G)  qual(R ? ⇧ (G), G). Proof. Consider qual(R T ⇧ (G), G) and qual(R ✓ ⇧ (G), G), and let S 1 2 R T ⇧ (G) and S 2 2 R ✓ ⇧ (G) be (one of) the route sets realizing this optimum. Since S 1 2 R T ⇧ (G) ✓ R ✓ ⇧ (G), we have in particular S 1 2 R ✓ ⇧ (G) and therefore qual(S 1 )  max S2R ✓ ⇧ (G) (qual(S, G)) = qual(R ✓ ⇧ (G),

C. Equivalence Under Symmetry

If routes are symmetric (using the same links in both directions), confluent routes are contained. Theorem 2. A symmetric and confluent routing model ensures that valid routes are contained.

Proof. For the sake of contradiction, assume the opposite for simple paths, i.e., two valid routes between nodes e and f , where a h 2 V s.t. g 2 R(e, f ); nodes e, g, f are incident to links in R(a, d), node g is not on any route in R(b, c), and e, f are on routes in R(b, c), e.g., like in Fig. 1. Consider T f = [ v2V R(v, f ), the confluent tree leading to f . Since T f is a tree, and since g 2 R(e, f )^(g, e, f ) 2 R(a, d) we deduce g 2 R(f, a) (or g 2 R(f, e) w.l.o.g.) due to symmetry. Since c,b) and due to symmetry we have a contradiction. The same argument can be generalized for walks using inports and attributes instead of loop-free paths.

T b [ v2V R(v, b) is also a tree, we have R(f, b) ⇢ R(e, b) ⇢ R(c, b) ⇢ T b . Thus g 2 R(

D. Routing Algebras Can Impact Coherence

As mentioned earlier, a routing algebra can be used to describe consistency properties: for each source-destination pair we can determine whether a route is preferred. Yet most routing algebras do not have an impact on coherence properties of sets of routes. However, some classes of routing algebras can be used to make statements about the kind of coherence properties a route set may not be able to satisfy. For example, results from [START_REF] Sobrinho | Network routing with path vector protocols: Theory and applications[END_REF], [START_REF] Rétvári | Compact policy routing[END_REF] can be interpreted with respect to coherence properties. To this end, we define the set of routes that represent all preferred paths of an algebra A by R A . An !-coherent route set S ✓ R A derived from A contains at most one route per source-destination pair. Furthermore, we need the definition of regular routing algebras, which feature a total order and satisfy monotonicity: w 1 w 2 L w 1 , 8w 1 , w 2 2 W and isotonicity:

w 1 w 2 =) w 3 L w 1 w 3 L w 2 , 8w 1
, w 2 , w 3 2 W . Monotonicity requires that prepending an edge (or path) of weight w 1 to another edge (or path) of w 2 can only make it less preferred. By commutativity, the same applies to appending edges/paths. Isotonicity, on the other hand, requires to be compatible with the semigroup (W, L ) in the following sense: if an edge/path is preferred over some other one, then prepending or suffixing both with a common edge or path maintains this relation. As an example, BGP and IGRP can both be represented by routing algebras. BGP is regular while IGRP is not isotonic and thus not regular [START_REF] Sobrinho | Network routing with path vector protocols: Theory and applications[END_REF]; a fact that illustrates how the above definitions can classify real-world routing policies. It also follows follows from [START_REF] Sobrinho | Network routing with path vector protocols: Theory and applications[END_REF] that an algebra A can be implemented by a destination-based routing function on any graph, if and only if A is regular. These results imply that a R A representing an algebra A can be turned into a confluent route set by removing some of the routes. In other words, a routing algorithm which selects one next hop based on the destination only and which conforms with algebra A, can exist if and only if A is regular and always produces a confluent route set. In other words, we can make the following observation.

Observation 1. A routing algorithm that turns a preferred route set R A into a !-coherent route set R 0 ✓ R A which is conf luent on every network exists if and only if A is regular.

Other aspects that have been studied for routing algebras are their scalability and memory requirements [START_REF] Sobrinho | Network routing with path vector protocols: Theory and applications[END_REF], [START_REF] Rétvári | Compact policy routing[END_REF]. Route sets that do not represent a regular algebra are incompressible in the sense that their policy does not scale well, as the memory needed to store the local routing process of some node increases with the number of nodes in at least one network topology.

Observation 2. Given a non-regular routing algebra A, there are networks where no !-coherent route set derived from R A for all source-destination pairs can be confluent.

On the other end of the spectrum, Retvari et al. [START_REF] Rétvári | Compact policy routing[END_REF] prove that if and only if a route set represents a monotonic and selective algebra, i.e., w 1 L w 2 2 {w 1 , w 2 } for each w 1 , w 2 2 W , this route set adheres to tree coherence and is thus highly compressible.

Observation 3. A route set R A representing a monotonic and selective algebra A is T -coherent.

E. Summary

To summarize our observations, coherence and consistency can have a large impact on the number of possible route sets on a given graph. As many networking problems involve exploring the space of possible route sets to find an optimal one, the impact of the routing model on the structure of this "potential solutions space" is twofold. First, by restricting the size of the solution space, constraining routing models can forbid the most optimal solutions (see Corollary 1). Second, by changing the nature of the solution space (e.g., its size), coherence also impacts the time complexity of algorithms, as well as the cost or performance of the solution. The next section provides examples that instantiate these differences on specific algorithmic problems.

IV. IMPLICATIONS FOR FUNDAMENTAL CASE STUDIES

So far we have shown how the model can affect the diversity and complexity of routing. Depending on the specific application, the diversity in turn affects the runtime and quality/cost of the solutions of the corresponding optimization problems. In this section, we describe two case studies demonstrating these impacts of the routing model.

Network Monitoring. When deploying a set of monitoring equipment on a subset of all nodes to observe the status of links, one possible optimization objective might be to use the minimum number of equipment (i.e., minimize deployment cost). Finding the right nodes for a deployment is NP-hard in many settings, while for some assumptions efficient exact or approximation algorithms exist [START_REF] Boothe | Graph covering via shortest paths[END_REF], [START_REF] Pignolet | Tomographic node placement strategies and the impact of the routing model[END_REF] for two versions of the problem with one or two types of monitoring equipment.

Note, that this monitoring problem cannot be addressed with tree routing, as not all links of a non-tree graph are used in this case and hence not all links can be monitored. Other routing models can be applied, with varying complexity and cost, provided each link is used in at least one route. In this context, the solution quality refers to the amount of equipment to be deployed: the lower the better.

Traffic Engineering. Consider a graph with capacitated links, i.e., each link has a maximum amount of traffic it can carry. We define congestion to be the ratio between the number of flows using an edge and its capacity. Given a set of requests (flows from v i to v j , for v i , v j 2 V ), the traffic engineering problem comes in different flavors: assigning routes to each flow, such that either (1) the maxmimum congestion is minimized or that (2) the routes are as short as possible and do not violate the capacity constraints. Both are multicommodity flow problems [START_REF] Even | On the complexity of time table and multi-commodity flow problems[END_REF]. The routing model to be used restricts solutions, i.e., the model is expressed as additional constraints in the multicommodity flow problem formulation. In this context, the notion of quality refers to the maximum congestion on a link resp. the length of a capacity-respecting path: lower is better.

A. Runtime

We first discuss the influence on runtime. Consistency Influences Runtime. One simple example showing that consistency influences complexity regards the traffic engineering of a single flow: in a directed network, it is easy and fast to compute a shortest capacity-respecting flow between a given source s and a destination t, e.g., by using Dijkstra's algorithm. However, computing a shortest capacity-respecting route from s to t that fulfills the policy that traffic must go through a single and given waypoint w, is NP-hard [START_REF] Amiri | Charting the algorithmic complexity of waypoint routing[END_REF].

Coherence Influences Runtime. The general unsplittable version of the load minimization problem (i.e., ! model) is NP-complete while optimal routes for arbitrarily splittable flows (⇤ model) can be found in polynomial time [START_REF] Even | On the complexity of time table and multi-commodity flow problems[END_REF]. For a variant of the traffic engineering problem, where instead of the concrete traffic matrix upper bounds on the weight of flows from and to nodes are given, a polynomial time algorithm computes an optimal tree routing scheme coinciding with the best possible loop-free confluent routing [START_REF] Fingerhut | Designing least-cost nonblocking broadband networks[END_REF], [START_REF] Gupta | Provisioning a virtual private network: a network design problem for multicommodity flow[END_REF].

We can show similar results when considering the monitoring problem for a graph where the routes are given. We rely on the consistency assumption that the routes use symmetric shortest paths below, regardless of the coherence model applied. It turns out that finding a monitoring deployment is NP-hard for the any, confluent and contained routing model on general graphs (an asymmetric version of this problem with two different types of equipment has been studied in [START_REF] Pignolet | Tomographic node placement strategies and the impact of the routing model[END_REF], the proofs therein can also be adapted to the symmetric case). For some restricted graph classes, differences in the complexity can be observed. In particular, a polynomial time algorithm can find an optimal assignment for cactus graphs for many routing policies, e.g., for confluent and contained routing (coinciding in this scenario, due to the symmetry), while it is NP-hard even in these graphs under the ! routing model.

Observe that in this case study, the routes are assumed to be given (or chosen by the adversary). In other words, solving the problem only consists in finding a deployment and not in finding a good set of routes as well. The combined routing and monitoring problem is still NP-hard on general graphs, using the same reduction as described above.

B. Quality

Next we study the quality of the optimizations.

Consistency Influences Quality. To study how consistency influences the admissible solution quality, we compare load minimization for different routing models. There exist examples where the minimum congestion achievable with shortest path routing for a given set of commodities exceeds the congestion achievable with other routing models by large factors.

For loop-free routing, Bley [START_REF] Bley | Approximability of unsplittable shortest path routing problems[END_REF] shows that the load obtained with shortest path routing can be up to ⌦(|V | 2 ) times larger than the minimum congestion achievable without this restriction. Furthermore, it is also a factor of ⌦(|V |) larger than the congestion of an optimal confluent routing.

Coherence Influences Quality. For the network monitoring example, we can observe on very simple graphs that the solution quality for different coherence models varies significantly, e.g., for the graph in Figure 4 due to the route diversity. For the model !, we can monitor at most x 2 different routes with shortest path monitoring pairs composed out of x nodes with monitoring equipment. If we can select the routes (i.e., when they are not chosen in an adversarial manner), we thus need at leastd p k/2e monitoring equipment for this scenario, deploying half of them on the source nodes on the left and the other half on the destination nodes on the right. For the routing models > and ✓ the minimum number of equipment we need is linear in k, even when selecting routes is possible.

For traffic engineering, Lorenz et al. [START_REF] Lorenz | How good can IP routing be?[END_REF] show that finding a loop-free minimum congestion confluent > route set is NPhard. They also show that the minimum congestion may be factor ⌦(|V |) higher for confluent routing than for the any ! routing model. Furthermore it is easy to see that a traffic engineering solution that is restricted to a tree can lead to a solution that is a factor of ⌦(n) worse than a confluent and contained solution, e.g. in a clique with uniform capacities and uniform all-to-all traffic demands.

V. EXAMPLE: OSPF

Most Internet routing protocols like OSPF and IS-IS conform to the shortest path consistency model, where each link is assigned a weight to represent its cost or length. Furthermore, unsplittable OSPF is confluent and depending on the link weight assignment and/or the selection of one of multiple shortest paths to a destination, OSPF also adheres to the contained routing model. Weights for a contained scheme can be determined efficiently if they exist. Theorem 3. (i) Given a loop-free contained scheme, we can find OSPF weights in O(poly(n)) if they exist. (ii) There are loop-free contained schemes for which no OSPF weights exist.

Proof. (i) Assigning weights to links in a set of routes such that unsplittable OSPF routing can be applied with unique shortest paths is known as the inverse unique shortest paths problem. Using linear programming techniques this problem can be solved in polynomial time [START_REF] Ben-Ameur | Internet routing and related topology issues[END_REF]. With this approach, the ratio between the smallest and highest weight is bounded by the minimum of the number of nodes divided by two and the number of routes in the routing scheme. Any walk including a cycle obviously cannot be described using weights as it is not a shortest path. (ii) Consider the set S = {(5, 6), [START_REF]Netkat: Semantic foundations for networks[END_REF][START_REF] Ben-Ameur | Internet routing and related topology issues[END_REF][START_REF] Boothe | Graph covering via shortest paths[END_REF], [START_REF] Amiri | Charting the algorithmic complexity of waypoint routing[END_REF][START_REF] Bley | Approximability of unsplittable shortest path routing problems[END_REF][START_REF] Boothe | Graph covering via shortest paths[END_REF], (4, 2, 6), (3, 1, 6)}. Since no two paths share two nodes, S constitutes a contained set. However it does not satisfy cyclic compatibility and can hence not be implemented with OSPF [START_REF] Ben-Ameur | Internet routing and related topology issues[END_REF].

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •

VI. EMPIRICAL MODEL DIVERSITY ANALYSIS

In this section, we take a closer a look at the routing model diversity available in various contemporary network topologies. More precisely, we here focus on shortest path consistent routing, and evaluate the number of complete route sets that are !-coherent and >-coherent and contain a route for each node pair, denoted by  ! and  > .

As we have seen in the previous section, the choice of a coherence model modifies the solution space of related applications, which in turn impacts both runtime and quality of the obtained solutions. We here empirically compare the size of those solution spaces, namely  ! and  > .

To conduct this numerical evaluation, we focus on 3 types of topologies. First, (LAN) datacenter topologies: we generate all Bcubes and Fat trees of size n  256 1 . Second, (WAN) zoo topologies 2 : we consider all zoo topologies of size n  256. Finally, d-regular random graphs are used to provide a synthetic baseline, with d = 3 (average degree of zoo topologies).

Figure 5 plots independently the diversity of both confluent and any for datacenter and zoo topologies. A first observation is the tremendous growth of both values. E.g., for F at(4) topologies (n = 99 nodes), the number of confluent route sets is in the order of 10 1408 and the number of any route sets in the order of 10 6740 . This observation holds for all topologies. The straight lines on the square-rooted scale suggest that the number of complete shortest path models is ⇡ 10 n 2 .

A second observation concerns the fraction of (any) route sets that are confluent, formally the ratio  ! |/ > . For instance, on F at(4), this ratio is 10 5332 which means that by sampling uniformly any-models, the probability of finding a confluent one is extremely low. This observation is confirmed also for the zoo datasets in Figure 6, which directly plots this ratio. This gap illustrates the considerable scale difference between 1 We use FNSS for topology generation [?]. 2 The Internet Topology Zoo http://www.topology-zoo.org/dataset.html. the any route set space, and the confluent route set space. As illustrated before, when optimizing routes for an application goal, this gap impacts both the quality of the optimal route set, and the exploration strategy of the solution space (which in turn impacts the runtime).

VII. RELATED WORK

Only little is known about the impact of the routing model on aspects beyond path diversity. A notable exception is the work by Erlebach et al. [START_REF] Erlebach | Cuts and disjoint paths in the valley-free path model of internet bgp routing[END_REF], [START_REF] Erlebach | Connectivity measures for internet topologies on the level of autonomous systems[END_REF] who study the computational complexity of routing, under consistency constraints, valid s-troutes and s-t-cuts, in the valley-free model. Kloeti et al. [START_REF] Kloti | Policy-compliant path diversity and bisection bandwidth[END_REF] proposed a generic method applicable to arbitrary graphs for policies which can be formulated as regular expressions (e.g., valley-free, (negative) waypoint routing multipath TCP). Most closely related to our work are [START_REF] Chekuri | Routing and Network Design with Robustness to Changing or Uncertain Traffic Demands[END_REF] and [START_REF] Pignolet | Tomographic node placement strategies and the impact of the routing model[END_REF]. Chekuri [START_REF] Chekuri | Routing and Network Design with Robustness to Changing or Uncertain Traffic Demands[END_REF] considers the problem of choosing routes for certain demand classes optimally with respect to the resulting congestion and the quality different coherence classes can attain in relation to each other. Chekuri also proposes a hierarchy which we extend in this paper. His any (!) property is called Single Path Routing (SPR), his confluent (>) property is called Terminal Tree Routing (TTR) and tree routing (T ) has the same name. We extend this hierarchy with contained (✓), which lies between the confluent and tree model. We also generalize the routing models by allowing to visit nodes multiple times. Pignolet et al. [START_REF] Pignolet | Tomographic node placement strategies and the impact of the routing model[END_REF] also introduce and compare routing models, however their work is restricted to coherence and does not account for consistency aspects; their results revolve around a specific case study.

VIII. CONCLUSION AND FUTURE WORK

This paper was motivated by the observation that the routing model, due to its constraints, can significantly influence the complexity and efficiency at which networks can be operated. We introduced a taxonomy of routing models accordingly and studied different implications. This also led us to question reasoning about network optimization problems in terms of the underlying physical topology only: this graph-centric view ignores the influence of the routing model. Sometimes a more restrictive coherence model does not affect route diversity much while introducing opportunities to speed up algorithms. We also found that tie-breaking among a set of consistent rules can have an impact on the efficiency of some protocols.

We hope that our perspective on consistent and coherent routing models can help the networking community identify novel optimization opportunities and reason about algorithms. In this regard, our paper also opens several interesting avenues for future research. In particular, it remains to explore the impact of the routing model on other performance criteria, e.g., memory/space complexity and on alternative applications, beyond traffic engineering and monitoring.

Fig. 1 .

 1 Fig. 1. Example: The routes from a and b to c and d are confluent: for each destination they follow the same route once they meet. The routes are not contained as paths between e and f differ.

2 Fig. 4 .

 24 Fig.[START_REF] Bley | Approximability of unsplittable shortest path routing problems[END_REF]. Graph illustrating the impact of the choice of routing policies on the route diversity. The route diversity in this graph is high for some models and low for others, implying a high variance in network problem solution quality for different routing models.

Fig. 5 .

 5 Fig. 5. Number of complete route sets adhering to shortest paths confluent and any routing models as a function of the topology size, for Fat Trees, BCubes and 3-regular random networks. The ordinate scale is square rooted.

Fig. 6 .

 6 Fig.6. The ratio between the number of any route sets and shortest path confluent route sets on zoo topologies. The ordinate scale is square rooted.

  ⇤find relay candidates⇤/ 2: if |C| > 1 /⇤ more than one relay candidate ⇤/ then

	3:	next hop =
	4:	forward packet to next hop
	5: else
	6:

Acknowledgments. Research supported by the ERC Consolidator project AdjustNet (grant no. 864228).