UNDERSTANDING, REDESIGNING AND IMPROVING FEED SELF-SUFFICIENCY IN LIVESTOCK FARMING

V. Thénard 1 , L. Laporte-Riou 1 , A. Dore 1 , D. Machado 2 , J. Ryschawy 3 1 INRA UMR-AGIR (France) ; 2 UFRGS (Brazil) ; 3 ENSAT UMR-AGIR (France)

-Introduction

In recent decades, the livestock farming model has resulted in a sharp increase in agricultural production. Livestock intensification was based on (i) the high production potential using selected animals and plants, (ii) the use of inputs to minimise the effects of environmental variability. In this context, a major challenge for livestock farmers is to simultaneously contribute to human food and nutritional security, based on limited resources, while reducing the negative impacts of agriculture on human health and the environment [START_REF] Duru | Livestock system sustainability and resilience in intensive production zones: which form of ecological modernization?[END_REF]. Many researchers propose agroecology as a promising way to overcome these challenges [START_REF] Dumont | Forty research issues for the redesign of animal production systems in the 21st century[END_REF][START_REF] Altieri | Technological Approaches to Sustainable Agriculture at a Crossroads: An Agroecological Perspective[END_REF]. In agroecological approaches, self-sufficiency appears as a central concept to improve the sustainability of livestock systems [START_REF] Magne | An integrated approach to livestock farming systems' autonomy to design and manage agroecological transition at the farm and territorial levels[END_REF].

For French dairy sheep, the high use of inputs affects farmers' incomes and degrades the viability of farms. An increase in feed self-sufficiency (FSS) could be a way to get off a relevant start for the agroecological transition, but according to different patterns of agroecological levers implemented by farmers [START_REF] Thénard | Quels leviers agroécologiques mobiliser pour la reconception de systèmes durables en brebis laitière ?[END_REF]. The redesign of the system toward improved the FSS must take into account the local and social characteristics of farmers and the supply chains. Despite this, the FSS implementation by farmers remains uncertain and scientists want to have a better understanding of their development conditions. In this article, we propose to identify among farmers and advisors the different perceptions of FSS and the means by which they intend to achieve them.

-Materials and methods

This study was carried out in the two main French dairy sheep areas producing PDO cheeses: Ossau-Iraty PDO for the department of Pyrénées Atlantiques; and Roquefort PDO for the departments of Tarn and Aveyron. The choice of these two regions should make it possible to identify levers for FSS, to compare and analyse in a context of two different socio-technical systems. We organized two participatory workshops in each region: one with advisers and technicians and the other with farmers. To design a shared representation of a FSS breeding system, we used a method using the serious LEGO® game. These workshops were followed by an individual approach with ten farmers' interviews.

-Results -Discussion

The issue of FSS is included in the PDO cheese specifications. All actors seem to consider that farms need to improve it to maintain the specific features of the cheeses. With LEGO® serious play, participants have built, step by step, a common livestock model based on essential internal components and their links with external actors of the livestock system (Figure 1). Those components were mainly defined by the diversity of grasslands and cultures. The links with external actors included supply-chains, agricultural development, banks, and social organisations. First, for farmers and technicians the FSS could be improve with different internal solutions: grazing management, increasing resource diversity, use of legumes in meadow… For all the groups, a shared way has identified to increase the FSS on farms: barn hay drying because this conservation process can improve the quality of fodder and therefore limit the supply of concentrate. However, this solution was considered at different scales in the two regions: at the farm level for Roquefort area ; and at the territory level for Ossau-Iraty area for collective use. Second, the issue of FSS is relevant at different levels in the two regions. For the Roquefort area, FDD is mainly defined at a farm level by improving it with technical solutions. For the Ossau-Iraty area, the FSS is developed on a territory scale and relies on cooperation between actors, for example between breeders and crop farmers. This territorial level involves interactions between mountains and plains and is a mean to achieve self-sufficiency at the territorial level.

During the individual interviews, farmers have explained their perception and levers usable for FSS development at the scale of their farm. The interviews have generally confirmed the results designed with LEGO® method. In the Ossau-Iraty area farmers had expressed the same perceptions of FSS and practices to implement it, independently of the type of farming systems. These convergences suggest that agricultural advice could be similar to improve the FSS for all farms. In the Roquefort area, farmers have expressed different levers to improve the FSS of their farm. Even though the majority of farmers has cited the barn hay drying, each of them suggests improving FSS by different ways: grazing management, crops development, high-diversity sown meadow use … Theses levers depend of the practices already used by farmers, and agricultural advice ought to be specific to improve the FSS for each farms.

-Conclusions

LEGO® serious play were used in different managerial contexts (governance, corporate strategy and management of transformations). In our project, the playful use of LEGO® serious play was an interesting method of design in agriculture. This collective design of the components of a livestock system allowed participants to exchange and build a common description of a FSS system without a priori. Beyond the technical dimensions, the FSS of a farm is reached when the farmer feels autonomous that means when I can decide about the strategic or management choices. This study is an important step for the agro-ecological transition of these local contexts. In addition, the study can contribute to challenge changes in livestock from the global to the local level identifying obstacles and levers for the transition.


Yann Guiguen

Jeremy Pasquier

Alexis Fostier

Julien Bobe
email: julien.bobe@inrae.fr

Evolution of sex hormone binding globulins reveals early gene duplication at the root of vertebrates

Keywords: evolution, Sex hormone-binding globulin, teleosts, vertebrates, gene expression

Phylogeny, synteny and expression analyses shed

Introduction

Sex hormone-binding globulin (Shbg) is mainly known as a blood-protein carrier involved in the transport of sex steroids in the plasma and in the regulation of their bioavailability to target organs. Shbg proteins present sequence similarities with the other LamG domaincontaining proteins growth arrest-specific 6 (Gas6) and protein S alpha (Pros1) [START_REF] Joseph | Sequence and functional relationships between androgen-binding protein/sex hormone-binding globulin and its homologs protein S, Gas6, laminin, and agrin[END_REF][START_REF] Joseph | Sex hormone-binding globulin, androgen-binding protein, and vitamin K-dependent protein S are homologous to laminin A, merosin, and Drosophila crumbs protein[END_REF]. By transporting and regulating androgens and estrogens access to the gonads, Shbg plays important roles in vertebrates reproduction [START_REF] Hammond | Diverse roles for sex hormone-binding globulin in reproduction[END_REF]. The Shbg protein was originally identified in the beta-globulin fraction of the human serum [START_REF] Rosner | Partial purification and preliminary characterization of estrogen-binding globulins from human plasma[END_REF] and has previously been known as Androgen-binding protein (Abp). Shbg genes and Shbg proteins have been characterized in a variety of tetrapod species with the notable exception of birds (Westphal, 1986;Wingfield et al., 1984). In aquatic vertebrates, Shbg was originally found in the plasma of an elasmobranch, the skate (Raja radiata) [START_REF] Freeman | Sex hormone binding proteins. II. Isolation from serum of an elasmobranch (Raja radiata)[END_REF], and of a teleost, the rainbow trout (Oncorhynchus mykiss) [START_REF] Fostier | Binding of steroids by plasma of a teleost: the rainbow trout, Salmo gairdneri[END_REF]. Since that moment on, Shbg have been subsequently identified and studied in many fish species (see for review [START_REF] Bobe | Diversity and biological significance of sex hormonebinding globulin in fish, an evolutionary perspective[END_REF]). Two different shbg genes i.e., shbga and shbgb, have been characterized in teleosts with shbga being the ortholog of the mammalian Shbg, which has been conserved from chondrichthyes to tetrapods and shbgb that has only been reported up to now in salmonids. In contrast to shbga that is mainly expressed in the liver [START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF], the shbgb transcript was mainly found in the ovary, suggesting a local mediation of the sex steroids effects by the Shbgb protein [START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF]. These two salmonid Shbg proteins share very low identity percentages, with for instance 26% identity between Shbga and Shgbb at the amino acid level in the rainbow trout [START_REF] Bobe | Diversity and biological significance of sex hormonebinding globulin in fish, an evolutionary perspective[END_REF][START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF]. In comparison to other vertebrates and teleost fishes, the salmonid ancestor has experienced an additional (4R) whole genome duplication known as the salmonid specific whole genome duplication, or SaGD [START_REF] Berthelot | The rainbow trout genome provides novel insights into evolution after whole-genome duplication in vertebrates[END_REF]. For this reason, and because no shbgb gene had ever been reported in a nonsalmonid species, it was first hypothesized that shbga and shbgb were ohnologous genes resulting from the SaGD [START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF]. This hypothesis was subsequently challenged in another study and the possibility of an ancient duplication followed by a lineage-specific retention in salmonids was suggested (Miguel-Queralt et al., 2009).

The evolutionary history of Shbg genes in vertebrates thus remained unclear and deserved further investigations. Using the increasing amount of genomic and transcriptomic data available for many vertebrate species we revisited the evolutionary history of Shbg genes.

The transcriptomes of 24 actinopterygian species (including 22 teleosts) and vertebrate genomes were included in the analysis, which led to the identification of previously noncharacterized Shbgb genes in several non-salmonid vertebrate lineages. Using phylogenomic analyses, we identified several Shbgb orthologs in a variety of non-salmonid vertebrate species, including teleosts, non-teleost actinopterygians, amphibians and one agnatha. Combined with synteny reconstruction analysis, we demonstrated that Shbg diversity results from a duplication event much older than the SaGD. To gain new information on the functional evolution of shbg genes, we also used quantitative PCR and next generation sequencing approaches, to characterize the expression profiles of shbga and shbgb transcripts for several actinopterygian species. This showed that the paralogous shbg genes have acquired different expression profiles with shbgb having a predominant gonadal expression contrasting with a predominant liver expression of shbga.

Material and Methods

Genomic and transcriptomic databases

Phylogenetic and synteny analyses

Amino-acid sequences of 126 predicted Shbg (a, b), Gas6 and Pros1 proteins were first aligned using ClustalW [START_REF] Thompson | CLUSTAL W: improving the sensitivity of[END_REF], then alignments were manually adjusted, to improve the quality of the multiple sequence alignments. The JTT (Jones, Taylor and Thornton) protein substitution matrix of the resulting alignment was determined using ProtTest software [START_REF] Darriba | ProtTest 3: fast selection of best-fit models of protein evolution[END_REF]. Phylogenetic analysis of the proteins presenting LamG domains (i.e. Shbga, Shbgb, Gas6 and Pros1) was performed using the neighbour joining (NJM) method (MEGA 5.1 software), with 1000 bootstrap replicates [START_REF] Tamura | MEGA5: molecular evolutionary genetics analysis using maximum likelihood, evolutionary distance, and maximum parsimony methods[END_REF]. Trees were edited online with iTOL [START_REF] Letunic | Interactive tree of life (iTOL) v3: an online tool for the display and annotation of phylogenetic and other trees[END_REF] and exported as Scalable Vector Graphics.

Synteny maps of the conserved genomic regions in human, Xenopus, coelacanth, spotted gar and zebrafish were constructed based on information available within the Genomicus [START_REF] Muffato | Genomicus: a database and a browser to study gene synteny in modern and ancestral genomes[END_REF]

RNA-seq shbga and shbgb tissue expression in holosteans and teleosts.

RNA-seq and de novo assembly were performed for all studied species as previously described [START_REF] Berthelot | The rainbow trout genome provides novel insights into evolution after whole-genome duplication in vertebrates[END_REF][START_REF] Braasch | The spotted gar genome illuminates vertebrate evolution and facilitates human-teleost comparisons[END_REF][START_REF] Pasquier | Gene evolution and gene expression after whole genome duplication in fish: the PhyloFish database[END_REF]. In order to study the expression patterns and levels of shbg transcripts for each actinopterygian species with two shbg genes, we mapped RNA-seq reads on the corresponding shbg coding sequence (CDS) using BWA-Bowtie [START_REF] Langmead | Fast gapped-read alignment with Bowtie 2[END_REF] with stringent mapping parameters (maximum number of allowed mismatches -aln 2). Mapped reads were counted using SAMtools [START_REF] Li | The Sequence Alignment/Map format and SAMtools[END_REF] idxstat command, with a minimum alignment quality value (q 30) to discard ambiguous mapping reads. For each species, the numbers of mapped reads were then normalized for each shbg gene across the eleven tissues using the reads per kilo base per million mapped reads (RPKM) normalization. All RNA-seq data are available here:

(http://phylofish.sigenae.org/index.html)

Quantitative PCR analysis (QPCR).

QPCR was performed using the RNA collections of the PhyloFish RNA-seq project as previously described [START_REF] Braasch | The spotted gar genome illuminates vertebrate evolution and facilitates human-teleost comparisons[END_REF][START_REF] Pasquier | Gene evolution and gene expression after whole genome duplication in fish: the PhyloFish database[END_REF]. Briefly, tissues were sampled from the same female individual and testis from a male individual, when possible. In some species and depending on the tissues, RNA samples from different individuals were pooled to obtain sufficient amounts of RNA. Total RNA was extracted using Tri-Reagent (Molecular Research Center, Cincinnati, OH, USA) according to the manufacturer's instructions. Reverse transcription (RT) was performed using 1 μg of RNA for each sample with M-MLV reverse transcriptase and random hexamers (Promega, Madison, WI, USA).

Briefly, RNA and dNTPs were denatured for 6 min at 70°C, chilled on ice for 5 min before the RT master mix was added. RT was performed at 37°C for 1 h and 15 min followed by a 15min incubation step at 70°C. Control reactions were run without reverse transcriptase and used as negative control in the real-time PCR study. Quantitative RT-PCR (QPCR) experiments were performed sing an Applied Biosystems StepOne Plus. RT products, including control reactions, were diluted to 1/25, and 4 μl were used for each PCR. All QPCR were performed in triplicates. QPCR was performed using a real-time PCR kit provided with a Fast-SYBR Green fluorophore (Applied Biosystems) with 200 nM of each primer in order to keep PCR efficiency between 80% and 100% for all target shbg genes. The relative abundance of target cDNA within a sample set was calculated from serially diluted cDNA pool (standard curve) using Applied Biosystem StepOne V.2.0 software. After amplification, a fusion curve was obtained to validate the amplification of a single PCR product. The fusion curves obtained showed that each primer pair used was specific of a single shbg transcript.

The negative control reactions were used to estimate background level. Genes were considered significantly expressed when measured level was significantly above background at p < 0.05 and within the range of the standard curve. For each studied tissue, cDNA originating from three individual fish were pooled and subsequently used for real-time PCR.

Before further analysis, real-time PCR data were collected using the same detection threshold for all studied genes. Data were subsequently normalized using the ΔΔCt method to 18S transcript abundance in samples diluted to 1:2,000.

Clustering analysis

Expression profiles originating from either QPCR and RNA-seq were represented using supervised clustering methods [START_REF] Eisen | Cluster analysis and display of genome-wide expression patterns[END_REF]. Hierarchical clustering was processed using centroïd linkage clustering, that uses the average value of all points in a cluster as a reference to calculate distance of other points, with Pearson's uncentered correlation as similarity metric on data that were normalized and median-centered using the Cluster program [START_REF] Eisen | Cluster analysis and display of genome-wide expression patterns[END_REF]. Results (colorized matrix) of hierarchical clustering analyses were visualized using the Java TreeView program [START_REF] Saldanha | Java Treeview--extensible visualization of microarray data[END_REF].

Results

Shbg gene evolution in vertebrates

In order to decipher phylogenetic relationships among Shbg sequences, a phylogenetic reconstruction of the evolution of Shbg was made based using the alignment of 126 vertebrate LamG domain-containing proteins. This phylogeny includes Shbg proteins, growth arrest specific 6 proteins (Gas6) and Vitamin K-dependent protein S (Pros1) and the tree was rooted using as outgroup the zebrafish Laminin subunit alpha 4 (lama4). This analysis (Fig. 1) shows that these vertebrate LamG domains proteins cluster into two major clades containing Shbg proteins on one side and the Gas6 and Pros1 proteins on the other side.

These Shbg and Gas6/Pros1 clades are both significantly supported with high bootstrap values (i.e. 75% and 100%, respectively). The Shbg clade contains two sub-clades both supported by significant bootstrap values. The Shbga cluster (100% bootstrap support), in red, contains all classical vertebrate Shbg proteins from chondrichthyes to teleosts with the notable exception of birds in which no Shbg proteins have been detected (see also Fig. S2).

The Shbgb cluster (93% bootstrap support), in blue, contains not only the salmonid Shbgb proteins, but also other vertebrate sequences outside the salmonid family including sequences from teleosts (European eel and silver arowana), non-teleost bony fishes (reedfish, spotted gar and bowfin), some amphibians and an agnatha, i.e., the sea lamprey (Fig. 1 and Fig. S1). The tree topology indicates that Shbgb proteins are not specific to the salmonids lineage and thus suggests a much more ancient origin of Shbgb genes in vertebrates than previously hypothesized [START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF].

To strengthen this phylogeny-based analysis of Shbg protein evolutionary history we carried out a synteny analysis in order to better support this hypothesis of an ancient origin Shbga and Shbgb genes. The synteny analysis first revealed that these two Shbg genes are located on two different syntenic chromosome regions in vertebrates (see Fig. 2A for the Shbga locus and Fig. 2B for the Shbgb locus). In contrast, Gas6 and Pros1 genes are located on the same syntenic chromosome region in most studied species, with the exception of primates (Fig. 2C). In vertebrates, Shbga, Shbgb, and Gas6/Pros1 are also located in regions containing other syntenic gene families. These neighboring genes are spread over four syntenic regions (Fig. 2A-2D) like for instance for the Atp-related genes (Atp1b2, Atp1b3, Atp4b) that are found in all four syntenic chromosome regions. In addition, Zbtbrelated genes (Ztb4, Zbt38, Zbt33) and Lamp-related genes (Lamp1, Lamp2, Lamp3) are present in three of the four different syntenic chromosome regions depending of the gene family. Altogether, these results strongly suggest that the diversity of the gene family present on these four syntenic chromosome regions probably results from early whole genome duplication events (VG1 and/or VG2) that occurred at the root of vertebrate evolution with a subsequent complex pattern of gene retention and gene losses.

Using the recently released salmonid genome resources, we also re-investigated the presence of additional copies of shbg genes in salmonids and confirmed that shbga and shbgb were both retained as single copies (Fig. 1) in rainbow trout, Atlantic salmon and coho salmon suggesting that no functional duplicated copies were retained after the salmonid whole genome duplication (SaGD). However, we also found an additional shbgb gene conserved in these three salmonid species (Fig. 3A), but with many stop codons in its deduced open reading frame (see example for rainbow trout in Fig. 3B), suggesting that this gene (ψ shbgb) was subsequently pseudogenized after the SaGD.

Expression patterns of shbga and shbgb

In all investigated actinopterygians, shbga was found to be mainly expressed in the liver, supporting a conserved role for this blood-secreted Shbg (Fig. 4). However, in the silver arowana a low shbga expression in the gonads is also detected in addition to the predominant liver expression (Fig. 4A and Fig. 4B). In contrast to shbga, expression of shbgb is not predominant in the liver in all investigated actinopterygians (Fig. 4A and Fig. 4B). In contrast, shbgb expression is predominantly detected in the gonads (ovary and/or testis) with the notable exception of the European eel.

In this study, we aimed at investigating the diversity of the Shbg family in vertebrates and the evolutionary history of Shbg genes. To date, despite the recent discovery of a second shbg gene (i.e. shbgb) in salmonids, the origin and diversity of Shbg genes in vertebrates has remained controversial. Because salmonids experienced an additional whole genome duplication (SaGD) approximately 100 Mya [START_REF] Berthelot | The rainbow trout genome provides novel insights into evolution after whole-genome duplication in vertebrates[END_REF][START_REF] Macqueen | A well-constrained estimate for the timing of the salmonid whole genome duplication reveals major decoupling from species diversification[END_REF] compared to other teleost fish and as shbgb genes were initially found in salmonids and, never reported at that time in any non-salmonid species, shbga and shbgb have been first hypothesized to be the result of the SaGD [START_REF] Bobe | Diversity and biological significance of sex hormonebinding globulin in fish, an evolutionary perspective[END_REF][START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF]. However pairwise comparison of Shbga and Shbgb reveals a surprisingly low sequence identity (around 25% at the amino acid level) that was initially interpreted as Shbga and Shbgb being highly divergent SaGD paralog. However, this paralogy relationship was not supported by the phylogeny reconstruction [START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF] and this discrepancy was thus explained as being the result of a long-branch attraction artifact resulting from the dramatic divergence of these two sequences [START_REF] Bobe | Diversity and biological significance of sex hormonebinding globulin in fish, an evolutionary perspective[END_REF][START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF]. Based on the cloning of another salmonid shbgb gene in coho salmon, Oncorhynchus kisutch and the low sequence identity between salmonids Shbga and Shbgb, other authors (Miguel-Queralt et al., 2009), hypothesized that the shbgb gene could stemmed from a much more ancient duplication than the SaGD. In order to decipher the evolutionary history of Shbg genes we re-analyzed the phylogenetic relationships of Shbg genes, their local synteny context, and the evolution of the phylogenetically and structurally closely related genes i.e., Gas6 and Pros1 that also contain LamG domains and are often identified as potential members of the same family. The identification of new Shbgb genes in vertebrates, the Shbg phylogenetic tree topology and their local synteny relationships strongly suggest that Shbga and Shbgb genes result from a whole genome duplication event that occurred very early at the root on the vertebrate lineage. The presence of a single Shbga gene and a single Shbgb gene in amphibians, holosteans, polypteriformes, agnatha and some teleost fishes, suggests that this Shbg duplication stems at least from the second round of vertebrate genome duplication (VG2). It is however also possible that Shbga and Shbgb originate the first round of vertebrate genome duplication (VG1) followed by the loss of one duplicate of each gene before VG2.

Following this early duplication, these two Shgb paralogs have evolved through many different phylum-specific gene retentions and/or gene losses. Among them the case of birds is interesting as they not only lost their Shbgb gene like reported here for many other tetrapods, but also their Shbga gene that is found to be conserved in all other vertebrates.

This complete absence of Shbga in birds has been already reported and it was hypothesized that this specific steroid hormone-binding transport would then be performed by a corticosteroid-binding globulin (Wingfield et al., 1984). Similarly, no Shbg homologs were detected by homology searches in Chondrichthyes (data not shown) but their complete absence in this clade requires further in-depth analysis and additional genome information as Shbg-like sex steroid binding capacities exist in the serum of the Thorny skate [START_REF] Freeman | Sex hormone binding proteins. II. Isolation from serum of an elasmobranch (Raja radiata)[END_REF]. In tetrapods, Shbgb was only found in Amphibians along with Shbga. Shbgb was also found in holosteans (spotted gar and bowfin), polypteriformes (reedfish), agnatha (sea lamprey) and in a few teleost fish orders i.e., in Elopomorphs (European eel), Osteoglossiforms (silver arowana) and Salmoniforms even though the protein is frequently misannotated in GenBank (Fig. S1). Interestingly we did not find any retention of additional whole genome [SaGD and the teleost specific duplication (TGD)] paralogs for both shbga and shbgb gene with the exception of a pseudogenized SaGD shbgb paralog (ψ shbgb). This indicates that these extra whole genome duplications did no impact the repertoire of shbg genes with a maximum of one shbga and one shbgb functional copies in all investigated teleost clades. This systematic and independent losses of additional shbga and shbgb duplicated paralogs in teleosts may reflect an evolutionary constraint of maintaining a correct gene and protein dosage as it has been suggested in other organisms [START_REF] Conant | Dosage, duplication, and diploidization: clarifying the interplay of multiple models for duplicate gene evolution over time[END_REF][START_REF] Gout | Maintenance and Loss of Duplicated Genes by Dosage Subfunctionalization[END_REF].

In consistency with existing data in mammals, our expression data showed that shbga is predominantly expressed in the liver in the different teleost species studied here. This confirms what has previously been reported in various teleost species including zebrafish (Danio rerio) [START_REF] Miguel-Queralt | Molecular and functional characterization of sex hormone binding globulin in zebrafish[END_REF], rainbow trout (Oncorhynchus mykiss) [START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF], Coho salmon (Oncorhynchus kisutch) (Miguel-Queralt et al., 2009), pejerrey (Odontesthes bonariensis) [START_REF] González | Sex hormone binding globulin: Expression throughout early development and adult pejerrey fish, Odontesthes bonariensis[END_REF] and sea bass (Dicentrarchus labrax) [START_REF] Miguel-Queralt | Sex hormone-binding globulin expression in sea bass (Dicentrarchus labrax L.) throughout development and the reproductive season[END_REF]. In addition, this strong hepatic expression is also observed in spotted gar (Lepisosteus oculatus) and bowfin (Amia calva) as shown by both RNA-seq and QPCR data.

In contrast to shbga, data on the tissue distribution of shbgb remain scarce. The ovarian predominant expression of shbgb was originally reported in rainbow trout, in which the transcript could also be detected at lower levels in muscle and stomach [START_REF] Bobe | A novel, functional, and highly divergent sex hormone-binding globulin that may participate in the local control of ovarian functions in salmonids[END_REF].

Semi quantitative data in Coho salmon confirmed the expression of shbgb in the ovary and stomach and revealed its presence in gills (Miguel-Queralt et al., 2009). Here we show that shbgb is also predominant expressed in the ovary in brown trout, silver arowana and grayling. We also report a strong testicular expression of shbgb in the two holostean species, spotted gar and bowfin, that appears to be lost in teleosts. In addition, the shbgb gene does not exhibit any gonad predominant expression in European eel. Together, our data show that shbga and shbgb have a very specific expression patterns with a predominant expression in liver and gonads, respectively. This pattern appears to be conserved during evolution without any significant change following whole genome duplications events (TGD and SaGD), with the exception of European eel in which the gonad predominant expression of shbgb appears to be lost. Finally, the strong testicular expression of shbgb revealed in bowfin and spotted gar is not found in any teleost species suggesting a specific role of Shbgb in testicular physiology in holostean species.

The multiple independent losses of Shbgb across vertebrates, while Shbga, Gas6 and Pros1

have been conserved in almost all vertebrates, could reflect different adapative and reproductive strategies as Shbg have been shown to be important carrier proteins for the blood transport of sex steroids and for their delivery to target reproductive tissues [START_REF] Hammond | Diverse roles for sex hormone-binding globulin in reproduction[END_REF]. However, despite this discrepancy among species, the distinct roles of Shgba in hormone transport in the blood and of Shbgb in local hormone action in reproductive organs as well as the associated expression in liver and gonads, respectively, appears to be evolutionary conserved in species that have retained both genes despite a few intriguing species-specific exceptions.

Acknowledgement

This work was supported by the French national research Agency (ANR-10-GENM-017-PhyloFish).

Figures Figure 1 :

 1 Figures

Figure 2 :

 2 Figure 2: Synteny maps of conserved genomic regions around LamG domains proteins (i.e. Shbga, Shbgb, Gas6 and Pros1) in human, Xenopus, coelacanth, spotted gar, Euroean eel, zebrafish and rainbow trout. Synteny maps are given for genomic regions around Shbga (A), Shbgb (B), Gas6 and Pros1 locus (C) and for a fourth region containing homologs of neighbouring Shbga, Shbgb, Gas6 and Pros1 genes (D). Genes are represented by blocks with an arrowed side indicating the gene orientation on chromosomes, linkage group or scaffolds. Gene location on chromosomes (Chr for Human and zebrafish), Linkage group (LG for spotted gar) and scaffolds (Ensembl reference or scaffold number) is given in Mb below each gene block. Genes belonging to the same Chr, LG or scaffolds are linked by a solid line.

Figure 3 :

 3 Figure 3: Multiple alignments plots of shbgb genes in salmonids. (A). Percentage of sequence identity of shbgb genes in Atlantic salmon, Salmon salar, and Coho salmon, Oncorhynchus kisutch compared to the rainbow trout, Oncorhynchus mykiss, shbgb gene on linkage group (LG) 24. In addition to the functional shbgb genes that were found in all salmonid species investigated, all these species have an additional shbgb homolog containing multiple stop codons and thus considered as a pseudogene (ψ shbgb). (B). Rainbow trout Shbgb and ψ Shbgb protein alignment showing that the ψ Shbgb contains multiple stop codons (red asterisks) and a large deletion in exon 4 of the Shbgb protein.

Figure 4 :

 4 Figure 4: Tissue expression profiles of shhbga and shbgb genes. (A). Heatmap (colorized matrix) of the hierarchical clustering of tissue RNA-Seq expression profiles (NGS values) of shbg genes in different Holostean (spotted gar and bowfin) and teleost species. A predominant expression of shbga is found in the liver contrasting with the predominant expression of shbgb in gonads (B). Heatmap (colorized matrix) of the hierarchical clustering of tissue expression profiles of shbg genes analyzed by quantitative PCR (QPCR values) in different Holostean (spotted gar and bowfin) and teleost species. Colorized matrixes highlight the high expressing tissues in yellow, the low expressing tissues in blue and the median expression in black (see color scale).

Figure 5 :

 5 Figure 5: Evolution of Shbg/shbg, Gas6/gas6, and Pros1/pros1 genes through successive whole genome duplications and independent gene losses. (A). Schematic representation of the evolution of LamG domains proteins including, Shbga (red squares), Shbgb (blue squares), Gas6 (purple squares) and Pros1 (green squares) in some jawed vertebrates' representative species. Whole genome duplications (black circles; VG1 and VG2: vertebrate genome duplications 1 and 2, TGD: teleost genome duplication, SaGD: salmonid genome duplication) are indicated at each duplication nodes. Gene losses are represented by square boxes with a cross inside. (B). Simplified representation of the evolution of Shbg proteins after whole genome duplications showing the systematic losses of one Shbga and Shbgb paralog after each duplication.

  Salmon salar, and Coho salmon, Oncorhynchus kisutch. Putative shbgb pseudogenes were retrieved by TBLASTN searches on whole genome sequences using as query the protein sequence of rainbow trout Shbgb.

			v75.01 website (http://www.genomicus.biologie.ens.fr/genomicus-
	75.01/cgi-bin/search.pl). Synteny map of the conserved genomic regions in the rainbow trout
	was	performed	using	the	Rainbow	Trout	Genomicus	Server
	(http://www.genomicus.biologie.ens.fr/genomicus-trout-01.01/cgi-bin/search.pl). The synteny
	analyses of European eel conserved genomic regions were obtained performing TBLASTN
	searches in the corresponding genomic database. For each studied gene, the protein
	sequences of human and zebrafish were used as queries.
	Multiple alignments plots of shbgb genes in salmonids were processed online
	(http://genome.lbl.gov/vista/) with mVISTA (Dubchak and Ryaboy, 2006; Poliakov et al.,
	2014) using genomic shbgb sequences of rainbow trout, Oncorhynchus mykiss, Atlantic
	salmon,

Supplementary Figures

Supplementary Figure 1: Phylogenetic trees of some vertebrate Shbga and Shbgb proteins. Protein sequences were searched in the ref-seq GenBank database using blastp (protein-protein BLAST) and in the the PhyloFish website (http://phylofish.sigenae.org/) using Shbga and Shbgb proteins from spotted gar (Lepisosteus oculatus, XP_015196088.1 and XP_015216776.1) and Western claw frog (Xenopus tropicalis, XP_0311755516.1 and KAE8604776.1) as baits. Phylogenetic analyses were performed on the Phylogeny.fr website (http://www.phylogeny.fr). Sequences were aligned with MUSCLE (v3.8.31) and cleaned with Gblocks (v0.91b) with default settings. Phylogenetic trees were reconstructed using the bayesian inference (A.) method implemented in the MrBayes program (v3.2.6), the maximum likelihood method (B.) implemented in the PhyML program (v3.1/3.0 aLRT) with 100 bootstrap replicates, and the neighbor joining method (C.) implemented in the BioNJ program. All trees were reconstructed with default settings and the graphical representation and edition of the phylogenetic tree were performed with TreeDyn (v198.3). Proteins and tree branches are depicted in blue for reptiles red for amphibians and in green for mammals. In panel C., the GenBank annotations are given for all protein sequences (with the exception of Shbg protein in Anguilla anguilla that were retrieved from the PhyloFish website), showing that all Shbga proteins are well annotated but that most Shbgb proteins are mis-annotated as Pros1-like or Gas6-like proteins.

Supplementary


Klaus-Tycho Foerster

Andrzej Kamisiński

Yvonne-Anne Pignolet

Stefan Schmid

Gilles Tredan

Grafting Arborescences for Extra Resilience of Fast Rerouting Schemes

To provide a high availability and to be able to quickly react to link failures, most communication networks feature fast rerouting (FRR) mechanisms in the data plane. However, configuring these mechanisms to provide a high resilience against multiple failures is algorithmically challenging, as rerouting rules can only depend on local failure information and need to be predefined. This paper is motivated by the observation that the common approach to design fast rerouting algorithms, based on spanning trees and covering arborescences, comes at a cost of reduced resilience as it does not fully exploit the available links in heterogeneous topologies. We present several novel fast rerouting algorithms which are not limited by spanning trees, but rather extend and combine ("graft") multiple spanning arborescences to improve resilience. We compare our algorithms analytically and empirically, and show that they can significantly improve not only the resilience, but also accelerate the preprocessing to generate the local fast failover rules.

I. INTRODUCTION

Communication networks have become a critical backbone of our digital society, as highlighted during the ongoing COVID-19 pandemic. As link failures become more likely with increasing network scale [START_REF] Gill | Understanding network failures in data centers: measurement, analysis, and implications[END_REF] and as even short disruptions of connectivity can cause severe degradation in service quality [START_REF] Alizadeh | Data center TCP (DCTCP)[END_REF]- [START_REF] Zats | Detail: reducing the flow completion time tail in datacenter networks[END_REF], it is important that networks detect such events quickly and reroute flows accordingly. This is hard to achieve using control plane mechanisms: reaction times in the control plane are known to be high [START_REF] Gill | Understanding network failures in data centers: measurement, analysis, and implications[END_REF]- [START_REF] François | Achieving sub-second IGP convergence in large IP networks[END_REF], not only due to global state advertisements and re-computations performed by widely deployed distributed control plane schemes such as OSPF [START_REF] Moy | OSPF version 2[END_REF] and IS-IS [START_REF] Iso | Intermediate Ststem-to-Intermediate System (IS-IS) Routing Protocol[END_REF], but also in emerging centralized schemes [START_REF] Greenberg | A clean slate 4d approach to network control and management[END_REF]- [START_REF] Yan | Tesseract: A 4d network control plane[END_REF].

To meet their stringent availability requirements, most modern communication networks hence feature local fast rerouting algorithms in the data plane which typically operates at timescales several orders of magnitude shorter than the control plane [START_REF] Liu | Ensuring connectivity via data plane mechanisms[END_REF], [START_REF] Feigenbaum | Brief announcement: on the resilience of routing tables[END_REF]: since rerouting decisions are local, failure recovery can in principle occur at the speed of packet forwarding. At the heart of such fast-reroute (FRR) mechanisms [START_REF] Chiesa | A survey of fast recovery mechanisms in the data plane[END_REF] lies the idea of pre-computing alternative paths at any node towards any destination. When a node locally detects a failed link or port, it can autonomously remove the corresponding entries from the forwarding table and continue using the remaining next hops for forwarding packets: a fast local reaction [START_REF] Stamatelakis | IP layer restoration and network planning based on virtual protection cycles[END_REF]. In FRR, the control plane is hence just responsible for pre-computing the failover paths; when a failure occurs, the data plane utilizes this additional state to forward packets. For example, many data centers use ECMP [START_REF] Kabbani | Flowbender: Flow-level adaptive routing for improved latency and throughput in datacenter networks[END_REF] (a data plane algorithm that provides automatic failover to another shortest path), WAN networks leverage IP Fast Reroute [START_REF] Papán | Overview of ip fast reroute solutions[END_REF]- [START_REF] Kamisiński | Evolution of IP fast-reroute strategies[END_REF] or MPLS Fast Reroute [START_REF] Pan | Fast reroute extensions to RSVP-TE for LSP tunnels[END_REF] to deal with failures on the data plane, SDNs provide FRR functionality in terms of OpenFlow fast-failover groups [START_REF]Switch Specification 1.3.1[END_REF], and BGP relies on BGP-PIC [START_REF] Cisco | Configuring BGP PIC Edge and Core for IP and MPLS[END_REF] for quickly rerouting flows, to just name a few.

However, while the local decision used by FRR enables fast reactions, it also introduces an algorithmic challenge: the failover behavior needs to be pre-defined, before the actual failures are known. Configuring FRR is hence particularly challenging under multiple and correlated failures [START_REF] Xu | Failure protection in layered networks with shared risk link groups[END_REF]- [START_REF] Elhourani | IP fast rerouting for multi-link failures[END_REF] since rerouting decisions need to be taken without knowledge of the failures downstream. Indeed, and while there has been much research on the topic over the last years [START_REF] Chiesa | A survey of fast recovery mechanisms in the data plane[END_REF], some of the most basic algorithmic problems are still open [START_REF] Chiesa | On the resiliency of static forwarding tables[END_REF].

This paper revisits the design of fast rerouting algorithms, aiming to provide a high resilience while using minimal assumptions on the required network functionality. In particular, we are interested in algorithms which do not require packet header rewriting during failover. Our work is specifically motivated by the observation that state-of-the-art solutions relying on spanning trees and arborescences, may result in a suboptimal resilience: in general, tree-based network decompositions can fail to exploit certain links which are vital for connectivity. We hence present several novel fast rerouting algorithms which are not limited by spanning trees, but rather extend and combine trees to improve resilience, a technique called grafting in botany. 1 We compare these algorithms analytically and empirically. In particular, we show that our approaches can significantly improve the resilience under different failure scenarios in comparison to the state of the art. Contributions. We present three new fast-failover routing schemes that retain worst-case guarantees but also leverage network heterogeneity for non-adversarial failure scenarios:

• §III: DAG-FRR utilizes the insight that disjoint routing trees can be extended to multiple directed acyclic graphs, greedily selecting the next hop closest to the destination. • §IV: Cluster-FRR is motivated by the observation that routing trees need not be rooted at the destination, but can also be formed in dense clusters, handing the packets over via exchange points (local roots) positioned at sparse cuts. • §V: Augment-FRR benefits from the fact that disjoint routing trees work well on homogeneous topologies (e.g., regular topologies), in turn augmenting the network in this direction with virtual links. When routing, Augment-FRR treats these virtual links like link failures.

Our extensive evaluations in §VI showcase the resilience gains over prior work, for various failure models (see §VI-A). In this context, to guarantee reproducibility and to allow other researchers to build upon our work, we have made the source code of our implementation of the algorithms publicly available at https://gitlab.cs.univie.ac.at/ct-papers/fast-failover. Additionally, it is worth noting that our algorithms also perform well while dealing with a small number of failed links.

Moreover, we prove in §II that some state-of-the-art schemes already fail for a single link failure, even though the network remains highly connected, see §VII for further related work.

Model. We will use the following terminology and model.

Network structure. We model the communication network as a graph G = (V, E), connecting |V | = n nodes (routers, switches, hosts) with E links. While bidirected (respectively full-duplex symmetric) links are common in networks, our algorithms also extend to strongly connected directed graphs. In the latter case, we might also use the term arc to emphasize the directed nature of a link. In this paper, we often distinguish between homogeneous and heterogeneous networks: the terms refer to the connectivity, that is, whether the connectivity between every node pair is the same or whether it can differ.

Routing and failover. We consider the common scenario where the static forwarding rules have to be precomputed and deployed at the nodes before the (unknown) link failures occur. In particular, we do not allow any packet modification, dynamic forwarding entry changes, convergence, or randomization: the forwarding rules may only match on the incoming port 2 , the destination t ∈ V , and the failure status of incident links. As such, FRR is purely local and comes into effect immediately.

II. MOTIVATION: LIMITATIONS OF THE STATE OF THE ART

In order to motivate our perspective and approach, we first revisit the state-of-the-art approaches for implementing FRR in our setting. We first consider arborescence-based FRR in §II-A, which performs well under worst-case failure scenarios and in homogeneous topologies. We then discuss the approach by Yang et al. [START_REF] Yang | Keep forwarding: Towards k-link failure resilient routing[END_REF] in §II-B, which utilizes adapted greedy forwarding in heterogeneous network structures. Afterwards, we draw conclusions for new and improved strategies in §II-C.

A. Homogeneous Networks: Arborescence-Based FRR

The fundamental idea of arborescence-based FRR is to leverage arc-disjoint spanning trees (arborescences) for forwarding: should a link fail, another arborescence can be selected, where the current arborescence is identified from the incoming port due to arc-disjointness. In more detail, given a k-link-connected graph, k arc-disjoint spanning arborescences rooted at a destination t can be found efficiently [START_REF] Bhalgat | Fast edge splitting and edmonds' arborescence construction for unweighted graphs[END_REF]. By using, e.g., a global circular permutation of the arborescences [START_REF] Chiesa | The quest for resilient (static) forwarding tables[END_REF], k-1 arc failures can be tolerated. An exemplary implementation is shown in Algorithm 1, using a given arborescence decomposition. 2 Without using the incoming port, already very simple link failure scenarios lead to permanent routing loops, as sending a packet back is impossible.

Algorithm 1: Circular Routing for Arborescences Upon receiving a packet destined for t at node v:

1: current arborescence T l (determined by in-port, else T 1 ) 2: if destination not reached yet, t = v then 3:

if next hop on T l available then update T l to be the next arborescence from the circular arborescence list From a worst-case perspective, resilience to k -1 arc failures is optimal, as k failures can disconnect a graph of connectivity k. Prior work utilized these worst-case guarantees to show benefits in highly homogeneous networks, such as for k -1 failures under k-connectivity [START_REF] Chiesa | On the resiliency of static forwarding tables[END_REF], but also multiple random failures in k-regular k-connected graphs and wellconnected cores of autonomous systems [START_REF] Foerster | CASA: congestion and stretch aware static fast rerouting[END_REF], [START_REF]Bonsai: Efficient fast failover routing using small arborescences[END_REF]. On the other hand, the arborescence approach gives no guarantees beyond the network's connectivity, and as such scales poorly for heterogeneous networks, e.g., if the network is 1-connected.

B. Heterogeneous Networks: Keep Forwarding FRR

Yang et al. [START_REF] Yang | Keep forwarding: Towards k-link failure resilient routing[END_REF] identified an approach to leverage topology heterogeneity, summarized as "Keep Forwarding" (KF): essentially, when the packet cannot be brought closer (down) to the destination in a greedy fashion, it tours the nodes of identical distance, until a not-failed down-link appears. In the absence of down-links and neighbors of identical distance, the packet takes a hop away from the destination, in order to find alternate routes. To avoid small loops, and as the only implicit memory of the forwarding function, the incoming port is only picked as the last resort, when all other incident links failed.

Yang et al. [START_REF] Yang | Keep forwarding: Towards k-link failure resilient routing[END_REF] show in their evaluations for 1, 2, and 3 link failures that KF retains over 99% reachability for heterogeneous autonomous systems and data center networks. Notwithstanding, no formal guarantee is claimed, not even for a single failure.

In the following, we show that KF already fails after a single failure, even if the remaining network remains highly connected. Consider the graph in Fig. 1, where the packet starts at node v 1 and has to be routed to the destination t. The next hop will be via the only down-link to v, but the link (v, t) has failed, resulting the packet to be forwarded up to some other node from v 2 , . . . , v k . While KF retains the knowledge not to route back via the inport to v, even though that is the only down-link, the next hop will be to another node from v 1 , . . . , v k . However, then the knowledge not to send the packet to v is lost (as the only memory is via the incoming port), and the packet is again forwarded to v, inducing a permanent forwarding loop. Moreover, observe that the network's connectivity remains at k ∈ Ω(|V |), i.e., arborescence-based FRR easily reaches the destination.

C. Reaping the Benefits of Both Approaches for New FRR

As we discussed above, arborescences have shortcomings when applied in heterogeneous networks, as they only utilize We would like to combine the benefits of both approaches: survivability w.r.t. worst-case failures, but also retain survivability against more failures in dense heterogeneous clusters. To this end, in the remainder of this paper, we extend the known arborescence-based approaches by incorporating non-spanning (partial) arborescences and local greedy routing, using them when classic arborescences fail. In this fashion, we retain the worst-case guarantees, but also utilize the path diversity in heterogeneous settings. We start in Section §III with a first approach that combines partial arborescences with directed acyclic graphs, followed by a more intricate arborescence construction in the following section.

t v v 1 v 2 v k u u 1 u 2 u k w 1 w 2 w k #hops

III. DAG-FRR: LEVERAGING HETEROGENEITY VIA DAGS

The idea of using directed acylic graphs (DAGs), instead of a forwarding tree (or arborescences), has already been proposed in [START_REF] Liu | Data-driven network connectivity[END_REF], [START_REF] Ray | Always acyclic distributed path computation[END_REF] (note however that these proposals do not fit into a purely local model, as they use message exchanges [START_REF] Ray | Always acyclic distributed path computation[END_REF] or link reversals [START_REF] Liu | Data-driven network connectivity[END_REF]): when the link to the next hop fails, the current node might have alternate next-hops, globally organized in a way such that no routing loops occur.

However, when only a single DAG is chosen, at least half of the available arcs (directed links) may not be used for routing: choosing both directions of a link for routing is a contradiction to the DAG property. For a simple example, consider routing on a ring topology: routing on a DAG already stops working after a single link failure, whereas arborescences can survive the same link failing. On the other hand, spanning arborescences perform poorly when the underlying connectivity is one. Here a DAG can contain a quadratic number of more links in the extreme case, which the arborescence leaves unused.

In this section we hence focus on combining DAGs and arborescences, to provide the best of both worlds. Instead of generating DAGs from scratch, we propose to extend arborescences to DAGs, meaning that our method can be understood as an extension of any arborescence structure, e.g., [START_REF] Chiesa | On the resiliency of static forwarding tables[END_REF], [START_REF]Bonsai: Efficient fast failover routing using small arborescences[END_REF], [START_REF] Foerster | Improved fast rerouting using postprocessing[END_REF], [START_REF]Local fast failover routing with low stretch[END_REF]. We emphasize that the underlying arborescences do not need to be spanning (as in prior work), partial rooted structures can be enhanced as well.

Our approach, henceforth called DAG-FRR, thus consists of three parts: §III-A describes how to build the partial arborescences, §III-B how to extend the arborescences, and §III-C how to extend the routing itself. We discuss in §III-D implications w.r.t. the worst-case resilience of DAG-FRR.

A. Part 1: Building Rooted Partial Arborescences

Prior work focused on building k arc-disjoint rooted spanning arborescences in k-connected graphs, even if the destination has a degree of k k. As such, in the common scenario that the network has a well-connected core that gets sparser in its outskirts, exactly the low connectivity of the outer regions defines the global survivability.

We overcome this restriction by building as many rooted arborescences as the destination can support by its number of neighbors. While not each of these arborescences can reach all nodes (i.e., be spanning), already a greedy approach will guarantee that every node is contained in at least one arborescence: else, there must be at least one node v, not in any arborescence, neighboring a node w in an arborescence T , a contradiction, as T can be extended from w to v.

We hence propose the following simple decomposition algorithm. We assign each of the k incoming arcs of the destination to a different arborescence T 1 , . . . , T k , and grow them greedily one after another, switching to the next arborescence T i+1 if no more nodes can be added to T i . Notwithstanding, this could leave many arcs unassigned to any arborescence, which we cover in the next subsection via arborescence extension.

B. Part 2: Extending Arborescences to DAGs

The underlying idea of our extension process is to utilize the so-far unused links and add them to the arborescence routing structures. As an input, we require a set of arborescences, or generalized, DAGs, and proceed as follows: For each DAG D i , we add unused arcs e to it, as long as: 1) D i with e is cycle-free, and 2) e connects to V (D i ).

We hence check all arcs if they can extend the given DAGs with the above two properties, repeating the process if some DAGs increased in size while doing so, see Algorithm 2.

C. Part 3: Extending Arborescence Routing

A fundamental strength of arborescence routing is that by considering the inport on which a packet arrives global information about the packet's journey so far can be inferred: the current node immediately knows which arborescence the packet is currently routed on, even though the packet remains unchanged. We thus strive to retain a packet in its current arborescence, which is easy in the case of DAGs: due to loop-freedom, at each node, each outgoing link of the current arborescence-DAG brings the packet closer to the destination.

A natural routing extension herein is to choose a surviving link that reduces the distance to the destination the most 3 , and 3 Though any choice from the set of outgoing links is viable. for all e = (u, v) / ∈ D do

6: if v ∈ V (D i ) then 7: if E(D i ) ∪ {e} is cycle-free then 8: E(D i ) ← E(D i ) ∪ {e} 9:
extended←true only switch to the next arborescence-DAG when all outgoing links of the current arborescence-DAG have failed. Note that the remaining routing logic stays intact and hence the routing extension can be implemented conceptionally as a simple subrouting, respectively an extension of the priority list of outgoing ports. We formalize this in Algorithm 3.

Algorithm 3: Circular Routing for DAGs

Upon receiving a packet destined for t at node v:

1: current DAG D l (determined by in-port, else D 1 ) 2: if destination not reached yet, t = v then 3:
if a next hop on D l available then Prior work already established that circular routing on k arc-disjoint rooted spanning arborescences is resilient to k -1 arc failures [START_REF] Chiesa | The quest for resilient (static) forwarding tables[END_REF]. The underlying reasoning is that after k -1 failures, at least one arborescence will be intact, i.e., the packet will eventually reach the destination. The invariant still holds for k arc-disjoint rooted spanning DAGs: by fixing a global circular order on the DAGs, one will eventually reach a failurefree DAG. We cast our observation into the following theorem: Theorem 1. Starting on k arc-disjoint rooted spanning arborescences/DAGs, DAG-FRR is resilient to k -1 arc failures.

We note that in §III-A we advocated for building partial rooted decompositions, instead of enforcing (fewer) spanning ones, to better leverage the network's heterogeneity, and might hence lose out on worst-case resilience. On the other hand, our DAG-FRR is flexible and can also start by employing a network decomposition that uses k arc-disjoint rooted spanning arborescences on k-connected topologies [START_REF] Bhalgat | Fast edge splitting and edmonds' arborescence construction for unweighted graphs[END_REF].

IV. CL U S T E R-FRR: LOCAL CLUSTER ALGORITHM

We now describe a more sophisticated arborescence decomposition algorithm, called Cluster-FRR. It applies a generic rooted spanning arborescence decomposition, e.g., the greedy algorithm also used in [START_REF] Chiesa | The quest for resilient (static) forwarding tables[END_REF]. The algorithm is based on local clusters: nodes having a positive clustering coefficient4 may form local regions of higher link connectivity relative to the entire graph. Here, algorithms computing the set of arc-disjoint spanning arborescences covering the graph would only return so many trees as is the value of the link connectivity of the graph, while the potential of the highly-connected regions would remain under-utilized. Indeed, by constructing additional arc-disjoint trees covering the highly-connected regions and using them to extend the primary set of arborescences, our algorithm (see Algorithm 4) is able to improve the fast recovery capabilities of a network in the case of multiple failures.

A. Cluster-FRR Arborescence Generation

The algorithm starts by computing a spanning arborescence decomposition of G rooted at the destination. Next, the clustering coefficient is determined for all nodes. Nodes for which the corresponding value is greater than zero are marked, together with their direct neighbors. Based on the previously marked nodes and the existing links between them, the subgraph G m of G is also created. Note that it is not required that subgraph G m be connected -in fact, as it comprises nodes and links belonging to each of the highly-connected regions of graph G, the next action is to decompose G m into stronglyconnected components and store them in set S m . The output set T out is also initialized to contain the arc-disjoint spanning arborescences stored in set T . When the graph is k-connected, T out at this point contains k arc-disjoint destination-rooted spanning arborescences T 1 , T 2 , . . . , T k .

Then, the algorithm considers each of the connected components G cc individually, ignoring those that contain less than three nodes. First, to improve the local link connectivity of G cc , all nodes of degree 1 are removed from G cc in a series of subsequent iterations of the while loop, until no more such nodes can be found in the graph. If the resulting graph contains less than three nodes or its link connectivity is less than two, G cc is rejected and the next connected component is considered instead. Second, the local root node r cc of the expected additional arborescences is selected in G cc based on the shortest distance to r in the original graph G. The arcdisjoint spanning arborescences rooted at r cc and covering G cc are then determined -the result is stored in set T cc . Next, the algorithm adds to set A all arcs of G cc that are included in one of the additional arborescences stored in T cc , except for the arcs being part of the primary arborescences already included in the output set T out . The main reason behind this selection process is to guarantee that no arc is assigned to multiple arborescences rooted either at r or r cc ; thus, that a failure of a single network link can disable at most two different arborescences associated with the related pair of opposite arcs. Each arc in set A is also Remove all nodes of degree 1 from G cc 13:

if |V cc | < 3 or LinkConnectivity (G cc ) < 2 then 14:
Proceed to the next iteration 15:

r cc ← GetClosestNodeToDestination (G cc , r) 16: T cc ← ArborescenceDecomposition (G cc , r cc ) 17:
A ← ∅ for all identifiers id among the elements of A do Current graph identifier: q ← LinkConnectivity (G) + A count + j 28:

Add (a, b) to the q-th graph in T out 29: j ← j + 1

30:

A count ← A count + s 31: return T out associated with the unique numeric identifier of the related arborescence. Finally, in lines 23 -28, the algorithm groups arcs associated with the same tree and transfers the resulting groups from A into the output set T out . Both the primary arborescences and the newly added groups of arcs are assigned unique numeric identifiers from a contiguous range (the primary arborescences have the lowest indices starting from 1).

B. Cluster-FRR Routing and Resilience

For k-connected graphs, Cluster-FRR generates a destination-rooted spanning arborescence decomposition T 1 , T 2 , . . . , T k , along with further non-spanning partial arborescences, with local root nodes and identifiers greater than k. Cluster-FRR then employs the circular arborescence-based routing scheme from Algorithm 1, starting in the arborescence with the lowest identifier. Hence, Cluster-FRR retains good worst-case guarantees: after up to k -1 arc failures, at least one of the primary spanning arborescences T 1 , T 2 , . . . , T k remains intact and can be used to route to the destination. In other words: Theorem 2. On k-connected graphs, Cluster-FRR is resilient to k -1 arc failures.

After more than k -1 arc failures, Cluster-FRR might need to resort to the local partial arborescences, and we can hence no longer provide the worst-case guarantees. On the other hand, the increased local survivability leads to greater resilience to non-adversarial failures, as we will see later in §VI.

V. AU G M E N T-FRR: CONNECTIVITY AUGMENTATION

So far, we proposed two methods that start with few arborescences, and then incorporate the remaining links, either by means of DAGs in §III or by building small local arborescences in §IV. In this section, we take a fundamentally different approach and start with many arborescences.

To this end, we augment the graph with virtual links to extend large local connectivity to the whole graph, build arborescences on top, and then remove these virtual links from the arborescences (hence they are no longer spanning) and let standard failover routing take over. In other words, we leverage that arborescences work well on homogeneous topologies.

In the following, we first describe how to augment the network efficiently to the desired level in §V-A and then cover in §V-B how to build the arborescences in a way that takes the distinction between virtual and real links into account.

A. Turning a Network Homogeneous

In order to maximize the efficiency of arborescence routing, a first step would be to obtain a network that is minimally k-connected, i.e., the removal of any bidirected5 link reduces the connectivity below k. In such networks, a rooted spanning arborescence decomposition can include every arc, except for the ones outgoing from the root.

A simple way of achieving this goal would be to turn the network into a clique K n , which however raises the question of how many virtual links we should include. On the one hand, we want to cover as many real arcs as possible with our augmentation, on the other hand, we want to include only few virtual links, as they disrupt the routing behavior.

To this end, we pick the node with the highest degree ∆ in the network (as each arborescence, for each node v = t, can only cover one outgoing arc of v), and augment the network to be ∆-connected. For bidirected graphs, this is a well-studied problem, and selecting the minimum number of links can be solved efficiently [START_REF] Frank | Augmenting graphs to meet edge-connectivity requirements[END_REF]. 6Hence, to summarize, Augment-FRR selects the largest degree ∆ in the network and then turns the network to be ∆-connected with a minimum number of virtual links.

B. Building Arborescences on Virtual Links

Building ∆ arc-disjoint rooted spanning arborescences on ∆-connected is well understood and can be computed efficiently [START_REF] Bhalgat | Fast edge splitting and edmonds' arborescence construction for unweighted graphs[END_REF]. However, in our context, we have to consider how to distribute real and virtual links over the arborescences.

Augment-FRR follows an approach that preserves worstcase resilience. To this end, it takes a ∆-connected network as the input, and then runs an greedy rooted spanning arborescence decomposition [START_REF] Chiesa | The quest for resilient (static) forwarding tables[END_REF] adapted to the problem at hand as follows: when growing arborescence T i , (1) a candidate arc a is only added if the remaining network, without T 1 , . . . , T i and without a is still be ∆ -i-connected, and (2), when multiple arcs can be selected for growing the arborescence T i , arcs belonging to real links are strictly preferred over virtual ones.

C. Augment-FRR Routing and Resilience

Augment-FRR utilizes circular arborescence routing from Algorithm 1 on the obtained decomposition, treating virtual links as link failures, in turn obtaining high resilience: Theorem 3. Augment-FRR achieves resilience to k -1 arc failures on k-connected graphs.

Proof: As proven in prior work [START_REF] Chiesa | The quest for resilient (static) forwarding tables[END_REF], using circular arborescence routing on k-arc disjoint t-rooted spanning arborescences achieves resilience to k -1 arc failures. It is left to show that Augment-FRR retains these worst-case guarantees. Observe that when building the arborescences, Augment-FRR leverages the greedy algorithm from Chiesa et al. [START_REF] Chiesa | The quest for resilient (static) forwarding tables[END_REF] in such a way, that real links always have preference over virtual links. Hence, as the greedy algorithm builds k arc-disjoint t-rooted spanning arborescences on the nonaugmented network, the greedy algorithm's output behavior will be identical for the first k arborescences on the augmented network. As such, virtual links will only be included from the k + 1 arborescence on.

As k -1 arc failures leave at least one of the first k arborescences unharmed, circular routing starting on arborescence T 1 will hence allow Augment-FRR to reach the destination.

VI. EVALUATION

To evaluate our approach and algorithms, we conducted extensive simulations. In general, whether the network will be able to restore the connectivity between any pair of nodes in the event of one or more link failures, depends on the structure of the network graph, and its link connectivity in particular.

In the following, we hence first present different link failure models for which we will evaluate our algorithms, and also describe the experimental setup. We then report on our main insights from our evaluation.

A. Link Failure Models

To investigate how the proposed solutions perform in different failure scenarios, we considered two different link failure models, denoted as RANDOM and CLUSTER. Random Link Failures (RANDOM). The first considered model introduces link failures uniformly at random across the entire network. It assumes that each link in the network has an equal probability of failure, and that none of the observed link failures result from targeted actions taken by malicious actors. Thus, in this model, we do not focus on how to take the maximum advantage of local redundancy -instead, we investigate how the network deals with multiple link failures in the general case. We also assume that each failure affects the corresponding network link in both directions. 7Targeted Attacks (CLUSTER). In this failure model, we try to capture more adversarial failures, e.g., due to an attack. We imagine that clusters in a network graph may represent well-connected regions, e.g., associated with groups of cities of strategic importance. In this context, the potential adversary might be interested in carrying out targeted and coordinated attacks against links belonging to one or more clusters, to degrade the fast-recovery capabilities of the network in the affected areas. Indeed, despite the relatively high connectivity in such areas, it is still possible that targeted link attacks will disrupt some of the precomputed or predefined primary and backup paths used by many data flows [START_REF] Cetinay | Comparing Destructive Strategies for Attacking Networks[END_REF]. Thus, the related challenge for the investigated fast-recovery algorithms is how to use the local redundancy in those regions to respond to targeted attacks effectively.

According to the considered model, failed links are selected as follows. First, the clustering coefficient is computed for all nodes in the network, and then, each arc incident to a node with a non-zero value of the clustering coefficient is added to the set F cand of candidate arcs that might be disabled, unless the set already contains the opposite arc. Second, as the number of failed bidirectional links is limited by one of the simulation parameters, f num , the following two cases are considered:

• |F cand | > f num : if the set

B. Experimental Setup and Metrics

Each of our experiments was performed based on the following general scheme, proceeding in five steps:

1) Given the topology of a network, a destination node t was selected uniformly at random from the set of all nodes. 2) Then, the precomputations to construct the routing tables were performed for each of the investigated algorithms and the time for these computation was measured separately for each algorithm. 3) In the next step, f num undirected links were selected as the failed network links based on one of the link failure models discussed in §VI-A. In addition, sample_size source nodes were chosen uniformly at random from the set of all nodes in the graph excluding the destination.

4) Then, the routing function was executed on the graph with f num failed links. some cases, the source nodes may no longer have been connected to the destination. 5) Finally, the success rate (defined as the number of data flows reaching the destination, divided by the number of all data flows) was computed separately for the investigated algorithms. The expected success rate for a perfectly resilient algorithm ρ is thus (n cc -1)/(n -1) where n cc denotes the number of nodes in the connected component of the destination after failures.

C. Routing Success in Highly Heterogeneous Networks

We first investigate the performance of our algorithms in highly heterogeneous networks in which connectivity varies significantly. To this end, we consider the following synthetic ring-of-cliques network topology model which contains several well-connected regions. Specifically, we assume that the network topology consists of L interconnected cliques (see Fig. 2), each having an internal link connectivity of k clique . Two adjacent cliques are connected by m bridge links incident to randomly chosen nodes on the two involved cliques, forming a graph for which the overall link connectivity is k graph ≥ min (k clique , 2m bridge ). To investigate the effectiveness of the considered algorithms in terms of their ability to deal with simultaneous failures of multiple network links, we further assume that k clique > k graph (the internal link connectivity of cliques is higher than the link connectivity of the entire graph).

C 1 C 2 C ... C L m bridge • • • • • • • • •
In our first experiment we vary the number of failed links the algorithms have to cope with and study their success rate. For randomly created rings of 10 cliques with k clique = 9 and m bridge = 2, i.e., graphs with 100 nodes and 470 links we observe the following behavior in Fig. 3: Under randomly chosen failures the three proposed algorithms are able to sustain around 100 link failures without any routing failures, while the pure Greedy Arborescence Decomposition and Keep Forwarding approaches exhibit routing problems already for as few as 10 failed links. When the number of failed links exceeds 100, the number of nodes in the connected component of the destination is below n, yet on average DAG-FRR, Cluster-FRR and Augment-FRR achieve a success rate of ρ, the expected success rate of a perfectly resilient algorithm for randomly chosen sources. When choosing the failed links with the cluster failure approach, see Fig. 4, Greedy and KF perform even worse. While KF gets stuck in local sinks as in Fig. 1, the Greedy method cannot leverage the local link diversity. On the other hand, our algorithms DAG-FRR and Cluster-FRR still reach ρ, while Augment-FRR is a bit below them on average. The reason is due to how Augment-FRR chooses the roots of partial non-spanning arborescences. Whereas Cluster-FRR picks them according to the distance to the destination, the corresponding choice for Augment-FRR is driven by the underlying connectivity augmentation algorithm, which takes this distance orientation only by a lesser degree into account. Similar in result to Cluster-FRR, DAG-FRR points q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.1 the additional arcs towards nodes that are closer to the destination, w.r.t. distance in routing along the current directed acyclic graph, and hence also performs well here.

D. Routing Success on Real-World Networks

We next evaluate the performance of our algorithms for the real-world network topologies collected as part of the Internet Topology Zoo project 8 Since the number of nodes and links in these graphs as well as their local and global connectivity varies considerably, we restrict ourselves to the subset of 122 topologies with 20 to 50 nodes and study the routing performance under random link failures.

To avoid cases where the destination is not connected to a significant number of nodes, we select them from the largest connected component after link failures. In Fig. 5 we present the success rate of the routing algorithms with respect to the percentage of nodes that are in the connected component of the destination after 10 random failures. We observe that DAG-FRR, Cluster-FRR, and Augment-FRR achieve a success rate of almost ρ, the expected success rate of a perfectly resilient algorithm for randomly chosen sources, while Greedy and Keep Forwarding perform less well.

Figure 6 provides a detailed look at the relative performance of our algorithms. It shows, for each Topology Zoo graph, the routing success rate of each algorithm normalized by the routing success of Cluster-FRR in the same graph. This allows for a more precise comparison of our algorithms: a point above y = 1 translates that the algorithm under scrutiny performed better than Cluster-FRR on the corresponding graph, whereas a point below translates a routing success rate under the one of Cluster-FRR. We omit Greedy for readability, and Cluster-FRR as all its corresponding datapoints lie on the y = 1 line by construction. Interestingly, DAG-FRR performs precisely identically to Cluster-FRR (all data points on y = 1). KF always performs worse than Cluster-FRR, especially on lightly impacted topologies (x > 0.5). Augment-FRR performs differently than Cluster-FRR, but with overall the same performance.

The gap between Augment-FRR and Cluster-FRR performances increases on heavily impacted topologies. The small amplitude of these differences can be explained by the performance of these algorithms: even on highly affected topologies, Augment-FRR, Cluster-FRR and DAG-FRR all rarely fail to route in the remaining connected component. As before, the underlying augmentation process of Augment-FRR explains its variance, but as we see here, there is a good set of topologies where Augment-FRR also performs better than all other algorithms.

E. Runtime to Compute Routing Tables

In order to evaluate how the precomputation time complexity of the algorithms scales in terms of the number of nodes in the network, we consider the ring-of-cliques network which is defined for any number of nodes by changing the number of cliques from 3 to 20 with 5 nodes per clique.

Figure 7 plots the runtime of the different algorithms, specifically showing the average wall clock time. Our results show that for all algorithms, the routing tables in networks with up to one hundred nodes can be precomputed in less than twenty seconds, rendering these algorithms practical in many scenarios. In fact, except for Augment-FRR which is significantly slower, all algorithms even complete in less than two seconds -an overhead we deem bearable, especially for infrequent updates. KF is significantly faster. However, as we have seen above, this comes at a price of reduced resilience.

VII. RELATED WORK

Failures are common in ISP networks [START_REF] Markopoulou | Characterization of failures in an operational IP backbone network[END_REF], [START_REF] Turner | California fault lines: understanding the causes and impact of network failures[END_REF], cloud provider WANs [START_REF] Govindan | Evolve or die: High-availability design principles drawn from googles network infrastructure[END_REF], and datacenters [START_REF] Gill | Understanding network failures in data centers: measurement, analysis, and implications[END_REF], [START_REF] Potharaju | When the network crumbles: an empirical study of cloud network failures and their impact on services[END_REF]. The design of fast rerouting algorithms has already been studied intensively q q q q q q q q q q q q q q q q q 0.1 in the literature. While there exists much interesting work on how to efficiently react to link failures in the control plane [START_REF] Jiang | PCF: provably resilient flexible routing[END_REF], [START_REF] Liu | Traffic engineering with forward fault correction[END_REF], e.g., using fast reconvergence techniques [START_REF] Busch | Analysis of link reversal routing algorithms for mobile ad hoc networks[END_REF], link reversal schemes [START_REF] Gafni | Distributed algorithms for generating loop-free routes in networks with frequently changing topology[END_REF], [START_REF] Corson | A distributed routing algorithm for mobile wireless networks[END_REF] or leveraging centralized approaches arising in software-defined networks [START_REF] Gafni | Distributed algorithms for generating loop-free routes in networks with frequently changing topology[END_REF]- [START_REF] Vahdat | A purpose-built global network: Google's move to SDN[END_REF], the reaction times provided by these solutions are significantly higher compared to fast failover mechanisms in the data plane [START_REF] Liu | Ensuring connectivity via data plane mechanisms[END_REF]: the focus of our paper. Data plane-based failover mechanisms are typically used as a first line of defense and also well-explored in the literature; implementations exist for most relevant protocols, IP [START_REF] Atlas | Basic specification for IP fast reroute: Loop-free alternates[END_REF], [START_REF] Rétvári | IP fast reroute: Loop free alternates revisited[END_REF] (including Segment Routing [START_REF] Bashandy | Topology independent fast reroute using segment routing[END_REF]- [START_REF]Local fast segment rerouting on hypercubes[END_REF]), MPLS [START_REF] Pan | Fast reroute extensions to RSVP-TE for LSP tunnels[END_REF], [START_REF] Jensen | P-rex: fast verification of MPLS networks with multiple link failures[END_REF], BGP [START_REF] Filsfils | Bgp prefix independent convergence (pic)[END_REF], SDN and programmable data planes [START_REF]Switch Specification 1.3.1[END_REF], [START_REF] Chiesa | PURR: a primitive for reconfigurable fast reroute: hope for the best and program for the worst[END_REF], among many more. We refer the reader to the recent survey by Chiesa et al. [START_REF] Chiesa | A survey of fast recovery mechanisms in the data plane[END_REF] for a literature overview on fast recovery schemes in the data plane.

Fast failover algorithms for the data plane can be categorized according to whether they require dynamic packet headers modifications (or even dynamic state at the routers), and according to which header fields a router needs to be able to match. By rewriting packet headers, it becomes possible to, e.g., carry failure information in the packets [START_REF] Elhourani | IP fast rerouting for multi-link failures[END_REF], [START_REF] Canini | A distributed and robust SDN control plane for transactional network updates[END_REF] or to employ classic graph exploration algorithms [START_REF] Borokhovich | Provable data plane connectivity with local fast failover: introducing openflow graph algorithms[END_REF], [START_REF] Reingold | Undirected connectivity in log-space[END_REF] as well as rotor router approaches [START_REF] Dereniowski | Bounds on the cover time of parallel rotor walks[END_REF], which can be exploited to render networks more resilient. However, this is often impractical, and is generally not supported. It is also known that in scenarios in which not only the destination field but e.g., also the source or the inport can be matched, the design of resilient fast failover algorithms is greatly simplified [START_REF] Chiesa | On the resiliency of static forwarding tables[END_REF], [START_REF] Chiesa | The quest for resilient (static) forwarding tables[END_REF], [START_REF] Chiesa | Exploring the limits of static failover routing (v4)[END_REF]. We also note that the focus in this paper is on deterministic algorithms, which, in contrast to related work such as [START_REF]On the resiliency of randomized routing against multiple edge failures[END_REF], [START_REF] Bankhamer | Local fast rerouting with low congestion: A randomized approach[END_REF], do not require random number generators at routers.

There already exist several interesting results on fast failover algorithms which do not require packet header rewriting. Feigenbaum et al. showed [START_REF] Feigenbaum | Brief announcement: on the resilience of routing tables[END_REF] that it is not always possible to achieve "perfect resilience" in this scenario, that is, it is not always possible to locally reroute packets to their destination even if the underlying network is remains connected after the failures; similar observations were obtained in parallel by Borokhovich and Schmid [START_REF] Borokhovich | How (not) to shoot in your foot with SDN local fast failover -A load-connectivity tradeoff[END_REF] who also derive bounds on what can be achieved in terms of load-balancing in such scenarios. Foerster et al. [START_REF] Foerster | On the feasibility of perfect resilience with local fast failover[END_REF] recently generalized the impossibility results related to connectivity by establishing a connection between graph minors and resilience; in particular, the authors showed that perfect resilience cannot be achieved on any non-planar graph, but is at least possible on outerplanar graphs.

The state-of-the-art approach to design highly resilient failover algorithms is based on arc-disjoint arborescence covers and is due to Chiesa et al. [START_REF] Chiesa | On the resiliency of static forwarding tables[END_REF], [START_REF] Chiesa | The quest for resilient (static) forwarding tables[END_REF], [START_REF]On the resiliency of randomized routing against multiple edge failures[END_REF]. This approach generalizes the widely-used approaches based on spanning trees [START_REF] Tapolcai | Sufficient conditions for protection routing in ip networks[END_REF]. However, while this approach may work well on graphs which are homogeneously k-connected (this is still an open question), it is not well-suited if directly applied to the general setting considered in our paper. In contrast, we in this paper have shown how to extend these concepts to more general and more heterogeneous networks.

The work closest to ours is by Yang et al. [START_REF] Yang | Keep forwarding: Towards k-link failure resilient routing[END_REF], who aim to go beyond the limitations of spanning trees and acyclic graphs by introducing what they call the partial structural network model. The authors show that this model indeed has several interesting features in practice. However, while their simulations look promising, the approach fails under worst-case failure scenarios. In particular, we have shown in this paper that even if the remaining connectivity is very high (linear in the number of nodes), a single arc failure suffices for their algorithm to fail. In contrast, our algorithms retain worst-case guarantees from arborescence approaches and can maintain k -1 arc failures, tolerating adversarial link failures.

VIII. CONCLUSION

This paper has studied how to extend existing fast failover mechanisms based on spanning trees and arborescences to improve the resilience of more heterogeneous networks whose connectivity varies across the topology. In particular, we presented three novel data plane algorithms which outperform stateof-the-art solutions in that they allow to maintain connectivity under significantly more failures.

From the three algorithms, our cluster and DAG algorithms perform relatively identical throughout our simulations, with our connectivity augmentation algorithm showing some slight variance in comparison. Due to our DAG algorithm having the fastest routing table precomputation time, we recommend it as a general choice amongst the three, but note that the augmentation algorithm sometimes performs slightly better, and hence a brief simulation for the intended topology might be worthwhile. To this end, and in order to guarantee reproducibility and allow other researchers to build upon our algorithms, we have made our code publicly available together with this paper.

We believe that our work opens several interesting avenues for future research. In particular, it remains to explore the resilience of our algorithms in more specific failure scenarios, both analytically and empirically. It would also be interesting to explore whether there are opportunities to improve our approach with randomization.

Algorithm 2 : 4 :

 24 DAG Extension Algorithm Input: Directed graph G = (V, E), arc-disjoint arborescences DAGs D = {D 1 , . . . , D k } Output: A maximal set D of arc-disjoint DAGs 1: extended←true 2: while extended=true do 3: extended←false for all D i ∈ D do 5:

4 :

 4 forward packet along outgoing arc in D l that reduces distance to t the most 5: else 6: update D l to next DAG from circular DAG list D. Part 4: Worst-Case Resilience Discussion

Algorithm 4 : 4 : 5 : 6 :

 4456 Cluster-Based Forest ConstructionInput: Directed graph = (V, E), destination r ∈ V Output: A set T out of rooted arc-disjoint spanning arborescences and additional directed acyclic subgraphs of G1: T ← ArborescenceDecomposition (G, r) 2: for all v ∈ V do 3: c v ← ClusteringCoefficient (G, v) if c v > 0 then Mark node v (not marked by default): m v ← 1 Mark all neighbors of v: ∀ u∈Neighbors(G,v) m u ← 1 7: G m ← Subgraph induced by the marked nodes 8: S m ← StronglyConnectedComponents (G m ) 9: T out = T , A count = 0 10: for all G cc = (V cc , E cc ) ∈ S m do 11:while |V cc | > 3 and MinDegree (G cc ) < 2 do 12:

18 :

 18 for all (a, b) ∈ E cc do 19: if (a, b) not included in any graph in T cc or (a, b) already included in a graph in T out then 20: Proceed to the next iteration 21: id ← GetArborescenceId (T cc , (a, b)) 22: A ← A ∪ (id, (a, b)) 23: s ← The number of unique arborescence identifiers among the elements of A 24:Index of an extra graph: j = 1 25:

26 :

 26 for all (a, b) associated with id in A do 27:

Fig. 2 .

 2 Fig. 2. Illustration of the ring-of-cliques network topology model. Each of the cliques C 1 , C 2 , . . . , C L has an internal link connectivity k clique and there are m bridge links between adjacent cliques.

Fig. 3 .

 3 Fig. 3. Routing success rates on the ring of cliques for varying number of RANDOM failures and for different algorithms. The black dashed line represents the average value of ρ, the percentage of the number of nodes in the connected component containing the destination (after failures), and is therefore a statistical upper bound on the success rate. Ribbons represent 1/4th of the standard deviation over 200 independent repetitions.

Fig. 4 .

 4 Fig. 4. Routing success rates on the ring of cliques for varying number of CLUSTER failures and for different algorithms. The black dashed line represents the average value of ρ, the percentage of the number of nodes in the connected component containing the destination (after failures), and is therefore a statistical upper bound on the success rate. Ribbons represent 1/4th of the standard deviation over 200 independent repetitions.

Fig. 5 .

 5 Fig.5. Routing success rates on the Topology Zoo dataset, as a function of the fraction of nodes remaining connected after 10 RANDOM failures. The black dashed line represents the average value of ρ, the percentage of the number of nodes in the connected component containing the destination (after failures), and is therefore a statistical upper bound of the success rate. A point (x, y) indicates that for a network topology on which 10 random link failures disconnect an average fraction of 1 -x nodes, the corresponding algorithm achieved a routing success rate of y.

Fig. 6 .

 6 Fig.6. Relative routing success rates of algorithms on the Topology Zoo dataset, for all graphs containing between 20 and 50 nodes, as a function of the fraction of nodes remaining connected to the destination after 10 RANDOM failures, compared to Cluster-FRR.

Fig. 7 .

 7 Fig.7. Average wall clock times for the precomputation of the routing tables of each algorithm on networks of increasing number of nodes. The shaded area symbolizes the 10 and 90 percentiles of the distribution sampled over 80 independent runs. The y-axis is square-rooted.

  of candidate arcs contains more elements than the value of f num , select f num arcs uniformly at random from set F cand and disable the corresponding bidirectional network links; • |F cand | ≤ f num : if the set of candidate arcs contains no more elements than f num , disable all bidirectional network links corresponding to arcs included in F cand .

Grafting is a technique to join two trees (and plants in general) into one. For example, many fruit trees today are grafted onto rootstock.

For the formal definition of the clustering coefficient in the context of graphs, the reader is referred to[START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF].

The problem can be defined analogously for directed networks, but we focus on bidirected full-duplex links given their prevalence in most networks.

We refer to Frank[START_REF] Frank | Augmenting graphs to meet edge-connectivity requirements[END_REF] for a discussion on further (directed) model variants.

We note that it would also be interesting to consider unidirectional link failures. For example, a recent data center study found that "only

[START_REF] Greenberg | A clean slate 4d approach to network control and management[END_REF].2% of the links [. . .] with packet corruption had bidirectional corruption"[START_REF] Zhuo | Understanding and mitigating packet corruption in data center networks[END_REF].

Acknowledgements: Research supported by the Vienna Science and Technology Fund (WWTF), grant ICT19-045, 2020-2024.