Nina Pelagie Bekono
email: ninapelagie.bekono@univ-bpclermont.fr

Nancy El Rachkidy
email: nancy.elrachkidy@univ-bpclermont.fr

Alexandre Guitton
email: alexandre.guitton@univ-bpclermont.fr

Fast loop-free transition of routing protocols

In networks that operate during a long time, the routing protocol might have to be changed (in order to apply a routing protocol update, or to take into account a change in the routing metrics). A loop-free transition algorithm has to be used in order to perform the transition to the new routing protocol without generating transient routing loops. In this paper, we propose a loop-free transition algorithm called ACH (avoiding cycles heuristic), which is able to perform the transition in a very small number of steps. Compared to other algorithms of the literature, ACH yields a number of steps which is independent of both the number of nodes and the number of destinations, and thus allows the transition to be performed in a small time. We show through simulations that ACH significantly outperforms other heuristics of the literature, due to its capability to deal with several destinations at once, and due to a priority-based procedure to avoid cycles.

I. INTRODUCTION

A routing protocol determines the routes followed by packets to their destination. In networks that operate during a long time, the routing protocol might have to be changed. This change might be required to apply a security update of the protocol [START_REF] Butler | A survey of BGP security issues and solutions[END_REF], to take into account significant modifications of the topology and link metrics [START_REF] Zhong | Avoiding transient loops through interface-specific forwarding[END_REF], [START_REF] Francois | Avoiding transient loops during the convergence of link-state routing protocols[END_REF], [START_REF] Nelakuditi | Mitigating transient loops through interface-specific forwarding[END_REF], or to handle urgent traffic in wireless sensor network monitoring applications [START_REF] Le Guennec | MAC protocol for volcano monitoring using a wireless sensor network[END_REF].

The transition from one routing protocol to another involves reconfiguring all routers in a given order. It is a complex and critical task: if the transition is not performed carefully, transient routing loops can occur, and the performance of the network can drastically decrease. Loop-free transition algorithms have been proposed in the literature to address this problem. RTH, proposed in [START_REF] Vanbever | Lossless migrations of link-state IGPs[END_REF], was the first heuristic to address this problem. It computes a router ordering that determines the order in which routers can perform the transition from a routing protocol R 1 to another routing protocol R 2 . However, the duration of the transition with RTH is proportional to the number of nodes in the network. RTHp and SCH-p, proposed in [START_REF] Rachkidy | Changing the routing protocol without transient loops[END_REF], allow the transition of some routers to be performed in parallel, reducing the transition time. However, the duration of the transition with RTH-p and SCH-p is proportional to the number of destinations in the network (for large networks). As most nodes are destinations, the overall transition duration is still large.

In this paper, we propose a loop-free transition algorithm called ACH (Avoiding Cycles Heuristic) that performs a transition in a small number of steps, independently of the number of nodes or destinations. ACH improves SCH-p on two aspects: [START_REF] Butler | A survey of BGP security issues and solutions[END_REF] it computes the cycles of every strongly connected component of the network and delays the transition of nodes that break the most cycles, which reduces the number of steps for each destination, and (2) it considers all destinations together, rather than considering them sequentially. The remainder of the paper is organized as follows. Section II describes relevant research works of the literature, and focuses on RTH, RTH-p and SCH-p. Section III presents ACH, first on one destination, and then on several destinations. Section IV presents and analyzes our simulation results. Finally, Section V concludes our work.

II. RELATED WORK ON LOOP-FREE TRANSITION

Initial research works on loop-free transition focused on the execution of a single routing protocol on a changing topology. In [START_REF] Zhong | Avoiding transient loops through interface-specific forwarding[END_REF], authors showed that with link-state routing, forwarding loops can occur when routers have a different view of the link metrics. They proposed a loop-less interface-specific forwarding approach that discards packets arriving through unusual interfaces, in order to remove these forwarding loops. The main drawback of their approach is that packets are dropped to prevent the formation of loops. In [START_REF] Francois | Avoiding transient loops during the convergence of link-state routing protocols[END_REF], authors showed that transient forwarding loops can occur when the network topology changes (which occurs due to link failures for instance). To solve this problem, they proposed a specific order in which routers can update their forwarding tables so that their consistency is ensured during the whole process of convergence. The main drawback of their approach is the convergence delay which can be large.

In this section, we briefly describe the three main heuristics that ensure a loop-free transition from R 1 to R 2 .

A. Routing Tree Heuristic (RTH)

RTH [START_REF] Vanbever | Lossless migrations of link-state IGPs[END_REF] separates destinations into two groups: nontroublesome destinations for which the transition can be performed simultaneously, and troublesome destinations for the others. Non-troublesome destinations are treated as a single destination, while troublesome destinations are treated individually. For each destination, RTH first identifies a set of per-destination constraints, and then computes a router ordering that satisfies all these constraints. Each per-destination constraint states that a node has to perform the transition after all its successors in the path to the destination. In more details, the process is as follows. For each destination d, a set S d of nodes that do not appear in any routing loop is computed with a greedy approach: initially S d contains d only. Then, each node which has both its next-hops (according to R 1 and to R 2 ) in S d is added to S d . All the nodes that have two different next-hops are added to a set V d . A set C d of constraints is built such that, for each path from a source node to a destination on R 2 , a constraint is generated for the last pair of nodes (u, v) with u ∈ V d and u / ∈ S d . A topological sort is computed in the acyclic directed graph G C d , built with all the nodes and arcs of C d . Then, nodes perform the transition one by one according to this topological sort.

The main drawbacks of RTH are the following. First, the authors did not specify the algorithm to identify nontroublesome destinations, as they did not experience many troublesome destinations. Second, nodes perform the transition one by one for each destination, which yields a long overall transition. In a network of n nodes and with d ∈ [1; n] destinations, if there are t ∈ [1; d-1] troublesome destinations, the transition duration of RTH is O((t + 1).n). Note that as n grows, t becomes closer to d (this is shown in both [START_REF] Rachkidy | Changing the routing protocol without transient loops[END_REF] and later in this paper, on Figure 4).

B. Routing Tree Heuristic with Parallel changes (RTH-p)

RTH-p [START_REF] Rachkidy | Changing the routing protocol without transient loops[END_REF] proposes two improvements of RTH-p. The first improvement is a greedy algorithm to identify as many nontroublesome destinations as possible. The second improvement is the use of parallelism: with RTH-p, it is possible to have several nodes performing the transition together (that is, in arbitrary order, and not necessarily simultaneously), without causing transient loops. In RTH-p, nodes perform their transition according to their distance (on R 2 ) to the destination. The main drawback of RTH-p is that for each destination, the transition produced by RTH-p is still relatively long. In a network of n nodes and d destinations, if there are t troublesome destinations, the transition duration of RTH-p is O(t. log n). Note that the term log n comes from the maximum depth of the tree formed by R d 2 for any destination d.

C. Strongly Connected components Heuristic with Parallel changes (SCH-p)

SCH-p [START_REF] Rachkidy | Changing the routing protocol without transient loops[END_REF] is based on strongly connected components to identify possible transient routing loops. SCH-p proceeds as follows. Each destination d is considered individually. For each destination d, a graph G d is built with arcs of R d 1 (if the node has not performed the transition yet) and of R d 2 (in all cases). Then, G d is partitioned into strongly connected components. For each strongly connected component, a set of nodes that can perform the transition without risking loops is computed. This set is computed greedily by adding nodes one at a time, until it is not possible to add new nodes without generating routing loops. Then, the step built by SCH-p is the union of all these sets for every strongly connected component. This process is repeated until all nodes have performed the transition to R d 2 . On Fig. 1, SCH-p computes the steps ({a, d, e}, {c}, {b}) for destination a, ({a, d, e}, {b}, {c}) for destination d, and ({d, e}, {c}, {b}, {a}) for destination e. Thus, the overall transition for SCH-p has ten steps: ({a, d, e} a , {c} a , {b} a , {a, d, e} d , {b} d , {c} d , {d, e} e , {c} e , {b} e , {a} e ). Note that when the network is small, RTH-p generally yields shorter transitions than SCH-p due to its ability to identify many non-troublesome destinations, but SCH-p outperforms RTH-p in medium to large networks [START_REF] Rachkidy | Changing the routing protocol without transient loops[END_REF] because the number of non-troublesome destinations in this case is very low and SCH-p generally produces less steps per destination.

The main drawback of SCH-p is that it considers all destinations individually (that is, all destinations are considered as troublesome destinations), which results into an overall duration of O(d), where d is the number of destinations.

III. FAST LOOP-FREE TRANSITION

ACH (Avoiding Cycles Heuristic) is a loop-free transition heuristic based on strongly connected components, as SCH-p. ACH aims to maximize the number of nodes that perform the transition at each step in order to reduce the total number of steps of the transition, and thus to reduce the transition duration. When the transition involves more than one destination, ACH first computes the steps for each destination independently, and then merges the steps together. Thus, we present in Subsection III-A how ACH operates for one destination, and in Subsection III-B how ACH operates for several destinations.

A. ACH for one destination

ACH operates as follows when there is only one destination. It first identifies all the cycles (using the algorithm from [START_REF] Johnson | Finding all the elementary circuits of a directed graph[END_REF]) in each strongly connected component. A cycle leads to a routing loop if and only if each node of the cycle routes within this cycle. Thus, avoiding a routing loop consists in finding at least one node in the cycle that routes outside the cycle. We say that such nodes break the cycle. More formally, a node n breaks a cycle C if n ∈ C and R 1 (n) / ∈ C. ACH attempts to find the smallest number of nodes that break all the cycles by using the following rules: (1) if a cycle is broken by a single node, this node is chosen first, and (2) nodes that break the largest number of unbroken cycles are chosen with higher priority. Once the set is computed, all the other nodes can perform the transition during the same step, and ACH proceeds to the next step by reapplying the same procedure on nodes that have not performed the transition yet. Algorithm 1 presents the core of the ACH algorithm, which is the algorithm that computes the set of nodes that break all cycles. S contains the nodes chosen by ACH to break all cycles (and thus, these nodes remain on R 1 during this step), and is initially empty. For each cycle C of the strongly connected component, the list of nodes that break C is computed. If a cycle is broken by a single node, this node is added to S. Then, the node of SCC \ S that breaks the most unbroken cycles is added to S, until every cycle is broken. Figure 3 shows an example of a network of twelve nodes. The elementary cycles are: c, g, k, j, f, e, a), C 8 = (a, d, i, k, j, f, e, a), C 9 = (a, c, g, k, j, f, e, b, a), C 10 = (a, d, h, g, k, j, f, e, a), C 11 = (a, d, i, k, j, f, e, b, a), andC 12 = (a, d, h, g, k, j, f, e, b, a). It is possible to compute the nodes that break each cycle. We obtain {c} for C 1 , {b, e} for C 2 , {g, k} for C 3 , {i} for C 4 , {f, i} for C 5 , {c} for C 6 , {g, j} for C 7 , {a, i, j} for C 8 , {e, g, j} for C 9 , {a, d, g, j} for C 10 , {a, e, i, j} for C 11 , and {a, d, e, g, j} for C 12 . Cycles that are broken by only one node are C 1 , C 4 and C 6 . Thus, nodes c and i are added to S. Note that these nodes also break cycles C 5 , C 8 and C 11 , which do not need to be broken by another node. Then, the node that breaks the most cycles is g (as it breaks five of the remaining cycles C 3 , C 7 , C 9 , C 10 and C 12 ), so g is added to S. With S = {c, g, i}, only C 2 remains. Both b and e can break C 2 , so b is chosen arbitrarily. The resulting set S is {b, c, g, i}, and the nodes that can perform the transition during the first step are {a, d, e, f, h, j, k, l}. For the second step, ACH considers that all nodes of the first step route according to R 2 (that is, R 1 ← R 2 ), and reapplies the same algorithm. The second step is thus {b, c, g, i}.

R a 1 R a 2 R d 1 R d 2 R e 1 R e
C 1 = (a, c, b, a), C 2 = (b, f, e, b), C 3 = (g, k, h, g), C 4 = (i, k, j, i), C 5 = (f, i, k, j, f ), C 6 = (a, c, b, f, e, a), C 7 = (a,

B. ACH for multiple destinations

ACH operates as follows when there are multiple destinations. It first computes the steps for each destination independently (see Algorithm 1). Then, it merges the steps for all destinations. Let us denote by step(i, j) the set of nodes of the i-th step of ACH for the single destination j. Then, the i-th step of ACH for all destinations is computed by merging the i-th step of each destination, that is step(i) = ∪ d j=1 step(i, j), where d is the number of destinations. Recall that on this network, RTH-p produced seven steps and SCH-p produced ten steps.

It can be noticed that the number of steps produced by ACH does not depend on the number of nodes of the network, nor on the number of destinations (as they are all merged by ACH). The number of steps produced by ACH depends on the largest number of steps for a single destination. Thus, the transition duration is O(1). The computation cost of ACH is larger with ACH than with RTH, RTH-p and SCH-p. However, we believe that it is more important for the transition to be fast than for the computation of the transition to be fast, as the computation can be done off-line.

IV. SIMULATION RESULTS

In this section, we compare the performance of our heuristic ACH with two other heuristics from the literature: RTH-p (which is an improvement of RTH) and SCH-p.

A. Performance metrics

The number of groups of compatible destinations indicates how a heuristic handles multiple destinations. A group of compatible destinations is the set of destinations which are treated together by a heuristic. For RTH-p, it is equal to t + 1, where t is the number of troublesome destinations (and 1 represents the set of all non-troublesome destinations, which are treated together). For SCH-p, it is equal to d, where d is the number of destinations, because each destination is treated independently. For ACH, it is equal to 1, because all destinations are treated together. This metric is mainly used to better understand the results of the other metrics.

The duration of the transition is our main metric, and it is computed as the overall number of steps of the transition. Here, we assume that one step corresponds to a time unit, as all nodes can be configured in parallel and can perform the transition in arbitrary order. The smaller is the number of steps, the faster is the transition.

The cost of the transition is the number of control messages required to perform the transition. It is equal to the sum of the number of distinct nodes per step, as each node has to be configured independently at each step where it appears. For example, for the transition ({d, e} ae , {c} ae , {b} ae , {a} ae , {a, d, e} d , {b} d , {c} d ), the first step generates two messages (for d and e, independently of the fact that two destinations are involved), the second one message (for c), the third one message (for b), the fourth one message (for a), the fifth three messages (for a, d and e), the sixth one message (for b) and the seventh one message (for c). The cost of the transition is thus ten.

B. Simulation settings

Our simulations are performed on random connected network graphs of size varying from 50 to 200 nodes. Nodes are deployed uniformly at random in an area of 100 m×100 m. The communication range of nodes is set to 20 m (which is a standard setup for wireless adhoc networks). We considered that each node is a potential destination. For each destination d, we generated R d 1 by assigning a random weight within [1; 100] to each link, and by computing the shortest path from each node to d using these weights. Similarly, we generated R d 2 by assigning a random weight within [1; 50] to each link, and by computing the shortest path from each node to d using these weights. Simulations are repeated 100 times, and a confidence interval of 95% is shown on plots.

C. Results

In the following, we present and analyze our simulation results on our three metrics. Note that all plots are shown with a logarithmic scale for the y-axis.

1) Number of groups of compatible destinations: Figure 4 shows the average number of groups of compatible destinations, for varying network sizes and for the three heuristics RTH-p, SCH-p and ACH. For ACH, the number of groups of compatible destinations is always one because ACH considers all destinations together. For SCH-p, this number is equal to the number of destinations d (which is equal to the network size in our settings), because SCH-p considers all destinations independently. For RTH-p, this number is between 1 and d. For networks of 50 nodes, nearly 30 destinations are nontroublesome (which allows RTH-p to consider only 21 groups of destinations: one for the 30 non-troublesome destinations, and 20 for the remaining 20 troublesome destinations). However, as the network size increases, non-troublesome destinations become less frequent. For networks of 200 nodes, only 3 destinations on average are non-troublesome.

2) Duration of the transition: Figure 5 shows the duration of the transition, computed as the average number of steps required to perform the transition for all destinations, for varying network sizes. We notice that the number of steps increases consistently with the size of the network for both RTH-p and SCH-p heuristics. For RTH-p, this is due to two factors: the increase in the number of groups of compatible destinations (see Figure 4), and the increase in the number of steps for each destination (due to the fact that the number of steps for each destination in RTH-p is equal to depth of the routing tree R d

2 ). For SCH-p, this is due to the increase in the number of destinations, as destinations are treated separately. ACH, however, is able to produce a very small number of steps, independently of both the number of nodes and the number of destinations, as its number of steps is equal to the maximum number of steps for every destination. ACH outperforms RTH-p with a gain varying from 98% for small networks up to 99% for large networks. Likewise, ACH outperforms SCH-p with a gain varying from 97% for small networks up to 99% for large networks. It is also important to note that, out of the 400 simulation results we obtained, ACH reached a maximum of 6 steps only once, and 5 steps or less for all the remaining simulations. It can be seen that the duration of the transition for ACH does not increase with the number of nodes nor with the number of destinations.

3) Cost of the transition: Figure 6 shows the cost of the transition, computed as the average number of control messages required to perform the transition for all destinations. For all heuristics, the number of control messages increases with the network size, as more nodes have to be configured overall. For large networks, RTH-p and SCH-p achieve similar results, which comes from the fact that these two heuristics are unable to merge destinations. The number of control messages is equal to n.d for SCH-p. For ACH, the small control overhead comes from the fact that all steps are merged: when a node appears several times in the same step for different destinations, it is counted only once as a single control message can configure the transition of this node for all destinations. In networks of 50 nodes, ACH outperforms RTH-p with a gain of 94%, and SCH-p with a gain of 97%. In networks of 200 nodes, the gain of ACH is 99% compared to both RTH-p and SCH-p.

V. CONCLUSION

The transition from one routing protocol to another routing protocol can lead to transient routing loops in networks. In this paper, we propose a fast loop-free transition algorithm called ACH. ACH focuses on identifying a small set of nodes that break cycles in strongly connected components, in order to ensure that many nodes can perform the transition in parallel, which reduces the overall transition duration. Compared to the main heuristics of the literature RTH-p and SCH-p, our simulation results on random networks show that ACH outperforms both of them. In term of the number of steps, the gain of ACH compared to RTH-p varies from 98% (for small networks) to 99% (for large networks), and the gain compared to SCH-p varies from 97% (for small networks) to 99% (for large networks). In term of the number of control messages, the gain of ACH compared to RTH-p varies from 94% (for small networks) to 99% (for large networks), and the gain compared to SCH-p varies from 97% to 99%.

  For a network of n nodes and d ∈ [1; n] destinations, we show through simulations that ACH performs the transition in O(1) steps (generally less than 5), RTH-p in O(d. log n) steps, SCHp in O(d) steps, and RTH in O(n.d) steps.

Figure 1

 1 shows an example of a network of five nodes, for three destinations (a, d and e) and two routing protocols per destination. RTH produces the order (a, e, d, c, b) for destination a, (d, e, a, b, c) for destination d, and (e, d, c, b, a) for destination e, as RTH considers destinations independently. The overall transition for RTH has fifteen steps. RTH-p identifies that destinations a and e are non-troublesome destinations, and computes the sequence of steps ({d, e}, {c}, {b}, {a}) for both destinations. Then, RTH-p computes the sequence of steps ({a, d, e}, {b}, {c}) for the remaining troublesome destination d. The overall transition for RTH-p has seven steps: ({d, e} a,e , {c} a,e , {b} a,e , {a} a,e , {a, d, e} d , {b} d , {c} d ).

Figure 1 .

 1 Figure 1. Example from [7] of routing protocols for three destinations: (a) a is the destination, (b) d is the destination, and (c) e is the destination.

Figure 2 2 Figure 2 .

 222 Figure 2 shows a small strongly connected component of four nodes, with two cycles C 1 = (a, b, c, a) and C 2 = (b, c, d, b). Nodes b and c break cycle C 1 . Indeed, if they do not perform the transition, they do not use R 2 and routing loop C 1 is impossible. Nodes b and d break cycle C 2 . Thus, ACH chooses the set {b}, as b breaks the largest number of cycles. Nodes of {a, c, d} can perform their transition in arbitrary order, without causing a routing loop.

Figure 1 Figure 3 .

 13 Figure3. A small network with twelve nodes and eleven elementary cycles, used as an example for ACH.

Figure 4 .

 4 Figure 4. Number of groups of compatible destinations as a function of the number of nodes, for the three heuristics.

Figure 5 .

 5 Figure 5. Duration of the transition as a function of the number of nodes.It can be seen that the duration of the transition for ACH does not increase with the number of nodes nor with the number of destinations.

Figure 6 .

 6 Figure 6. Cost of the transition as a function of the number of nodes, for the three heuristics. Due to a small number of steps, ACH is able to perform the transition for all destinations with a limited overhead.

ACKNOWLEDGMENT

This work has been sponsored by the French government research program "Investissements d'avenir" through the IMobS3 Laboratory of Excellence (ANR-10-LABX-16-01), by the European Union through the regional program competitiveness and employment 2014-2020 (ERDF -Auvergne region), and by the Auvergne region.