Serafino Cicerone
email: serafino.cicerone@univaq.it

• Gianlorenzo
email: gian-lorenzo.dangelo@inria.fr

D ' Angelo

Gabriele Di
email: gabriele.distefano@univaq.it

Daniele Frigioni
email: daniele.frigioni@univaq.it

Vinicio Maurizio
email: vinicio.maurizio@cc.univaq.it

G D'angelo

Keywords: Shortest Paths, Distributed Networks, Dynamic Algorithms, Concurrent Update, Experimental Analysis

We study the problem of dynamically updating all-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes.

In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO's widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford.

Engineering a new algorithm for distributed shortest paths on dynamic networks 1 Introduction

The problem of efficiently updating all-pairs shortest paths in a distributed network whose topology dynamically changes over the time, in the sense that link weights can be modified during the lifetime of the network, is considered crucial in today's practical applications. Hence, it is very important to find efficient dynamic distributed algorithms for shortest paths. This problem has been widely studied in the literature, and the solutions found can be classified as distance-vector and link-state algorithms.

Distance-vector algorithms require that a node knows the distance from each of its neighbors to every destination and stores this information in a data structure usually called routing table. A node uses its own routing table to compute the distance and the next node in the shortest path to each destination. Most of the distance-vector solutions for the distributed shortest paths problem proposed in the literature (e.g., see [START_REF] Cicerone | Partially dynamic efficient algorithms for distributed shortest paths[END_REF][START_REF] Cicerone | A fully dynamic algorithm for distributed shortest paths[END_REF][START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF][START_REF] Humblet | Another adaptive distributed shortest path algorithm[END_REF][START_REF] Italiano | Distributed algorithms for updating shortest paths[END_REF][START_REF] Orda | Distributed shortest-path and minimum-delay protocols in networks with time-dependent edge-length[END_REF][START_REF] Ramarao | On finding and updating shortest paths distributively[END_REF]) rely on the classical Distributed Bellman-Ford method (DBF from now on), originally introduced in the Arpanet [START_REF] Mcquillan | Adaptive routing algorithms for distributed computer networks[END_REF], which is still used in real networks and implemented in the RIP protocol. DBF has been shown to converge to the correct distances if the link weights stabilize and all cycles have positive lengths [START_REF] Bertsekas | Data Networks[END_REF]. However, the convergence can be very slow (possibly infinite) due to the wellknown count-to-infinity phenomenon also know as routing table looping. A loop is a path induced by the routing table entries, such that the path visits the same node more than once before reaching the intended destination. A node "counts to infinity" when it increments its distance to a destination until it reaches a predefined maximum distance value. Furthermore, if the nodes of the network are not synchronized, even though no change occurs in the network, the overall number of messages sent by DBF is exponential in the size of the network (e.g., see [START_REF] Awerbuch | Approximate distributed bellman-ford algorithms[END_REF]).

Link-state algorithms, as for example the Open Shortest Path First (OSPF) protocol widely used in the Internet (e.g., see [START_REF] Moy | OSPF -Anatomy of an Internet routing protocol[END_REF]), require that a node knows the entire network topology to compute its distance to any network destination (usually running the centralized Dijkstra's algorithm for shortest paths). Link-state algorithms are free of count-to-infinity, however each node needs to receive and store up-to-date information on the entire network topology after a change, thus requiring quadratic space per node. This is achieved by broadcasting each change of the network topology to all nodes [START_REF] Moy | OSPF -Anatomy of an Internet routing protocol[END_REF][START_REF] Rosen | The updating protocol of arpanet's new routing algorithm[END_REF][START_REF] Wu | An extended fault-tolerant link-state routing protocol in the internet[END_REF] and by using a centralized dynamic algorithm for shortest paths as for example those in [START_REF] Frigioni | Fully dynamic algorithms for maintaining shortest paths trees[END_REF][START_REF] Narváez | New dynamic algorithms for shortest path tree computation[END_REF].

If the topology of a dynamic network is represented as a weighted undirected graph, then the typical update operations on that network can be modeled as insertions and deletions of edges and edge weight changes (weight decrease and weight increase). When arbitrary sequences of the above opera-tions are allowed, we refer to the fully dynamic problem; if only insertions and weight decrease (deletion and weight increase) operations are allowed, then we refer to the incremental (decremental ) problem. We are interested in the practical case of a dynamic network in which an edge change can occur while one or more other edge changes are under processing. A node (processor) v of the network might be affected by a subset of these changes. As a consequence, v could be involved in the concurrent executions related to such changes.

Many algorithms proposed in the literature for the dynamic distributed shortest paths problem are not able to concurrently update shortest paths as those in [START_REF] Cicerone | A fully dynamic algorithm for distributed shortest paths[END_REF][START_REF] Italiano | Distributed algorithms for updating shortest paths[END_REF][START_REF] Orda | Distributed shortest-path and minimum-delay protocols in networks with time-dependent edge-length[END_REF][START_REF] Ramarao | On finding and updating shortest paths distributively[END_REF]. In particular, they work under the assumption that before dealing with an edge operation, the algorithm for the previous operation has to be terminated. This is a limitation in real networks, where changes can occur in an unpredictable way. For example, the algorithm proposed in [START_REF] Cicerone | A fully dynamic algorithm for distributed shortest paths[END_REF] to handle weight increase operations works in three phases, and each phase starts when the previous one is completed. In a concurrent scenario, a new edge update can stop one of these phase thus making the algorithm incorrect. Among the algorithms which are able to concurrently update shortest paths (see, e.g., [START_REF] Cicerone | Partially dynamic efficient algorithms for distributed shortest paths[END_REF][START_REF] Cicerone | Partially dynamic algorithms for distributed shortest paths and their experimental evaluation[END_REF][START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF][START_REF] Humblet | Another adaptive distributed shortest path algorithm[END_REF][START_REF] Ray | Always acyclic distributed path computation[END_REF]) the most interesting is DUAL (Diffuse Update ALgorithm) [START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF], which is free of the count-to-infinity phenomenon, thus resulting an effective practical solution (it is in fact part of CISCO's widely used EIGRP protocol).

An incremental and a decremental solution have been proposed in [START_REF] Cicerone | Partially dynamic algorithms for distributed shortest paths and their experimental evaluation[END_REF]. Such solutions cannot deal with fully dynamic sequences of edge weight changes and the decremental solution suffers of count-to-infinity. In this paper, we extend the decremental solution of [START_REF] Cicerone | Partially dynamic algorithms for distributed shortest paths and their experimental evaluation[END_REF] by providing a new concurrent and fully dynamic algorithm for the distributed shortest paths problem denoted as DUST (Distributed Update of Shortest paThs). DUST suffers of the countto-infinity problem, but it has been designed to heuristically reduce the cases where this phenomenon occurs. If we denote as n the number of nodes in the network, as deg(v) the degree of a node v, and as maxdeg the maximum node degree, DUST requires the same worst-case space occupancy per node of both DBF and DUAL that is O(n • maxdeg). However, DBF and DUAL store, for each node v, a data structure whose size is proportional to n • deg(v). In fact, they store specific information on each neighbor u of v, as for example, the distance from u to any other node s. Instead, DUST simply stores at node v the distance from v to s and all possible alternative vias to s, and does not store any information regarding its neighbors. This means that the space required by DUST depends on the node degree only in the worst case, which indeed occurs very rarely. In most of the cases the space occupancy of DUST does not depend on the node degree. For these reasons, it is worth measuring the practical performance of DBF, DUAL, and DUST in various dynamic realistic and artificial scenarios, in terms of both the overall number of messages they send, and their space occupancy per node.

With this goal in mind and following an algorithm engineering approach, we implemented DBF, DUAL, and DUST in the OMNeT++ simulation environment [START_REF]Omnet++: the discrete event simulation environment[END_REF], an object-oriented modular discrete event network simulator which is widely used in the literature. As input to the algorithms, we used both realworld and artificial instances of the problem. In detail, we used snapshots of the Internet graph provided by the CAIDA IPv4 topology dataset [START_REF] Hyun | The CAIDA IPv4 routed/24 topology dataset[END_REF]. CAIDA (Cooperative Association for Internet Data Analysis) is an association which provides data and tools for the analysis of the Internet infrastructure. Then, we used random Internet-like topologies with a power-law node degree distribution, generated by the Barabási-Albert algorithm [START_REF] Albert | Emergence of scaling in random networks[END_REF]. Power-law networks have been proven to model many real-world networks such as the Internet, the World Wide Web, citation graphs, and some social networks [START_REF] Albert | Statistical mechanics of complex network[END_REF]. Finally, since both CAIDA graphs and Barabási-Albert graphs turn out to be very sparse, we also analyzed random dense graphs generated by the Erdős-Rényi algorithm [START_REF] Bollobás | Random Graphs[END_REF].

The experiments performed show that the space occupancy per node required by DUST is much smaller than that required by both DBF and DUAL. In terms of number of messages sent, DUST outperforms both Bellman-Ford and DUAL on the Internet topologies provided by CAIDA. In Barabási-Albert artificial instances, DUST sends more messages than DUAL but fewer than Bellman-Ford. In the case of Erdős-Rényi artificial instances, DUAL is still better than DUST in terms of number of messages, while we noticed a big increase in the space occupancy per node required by DUAL. In all our experiments, we observed that both DUAL (as expected) and DUST never counts to infinity, while in many cases DBF does. The last observation confirms the effectiveness of the heuristics implemented in DUST to reduce the cases where the count-to-infinity phenomenon occurs.

Finally, we compared DUST with the incremental and decremental solutions of [START_REF] Cicerone | Partially dynamic algorithms for distributed shortest paths and their experimental evaluation[END_REF], which are denoted from now on as INC and DEC, respectively. The comparison has been done separately, once for sequences of only weight increase operations and once for sequences of only weight decrease operations. While the space occupancy per node is always comparable, in term of number of messages sent, in the incremental case, DUST is slightly worse than INC and, in the decremental case, it is slightly better than DEC.

The paper is organized as follows. In Section 2 we describe the model and the notation used in the paper and the DBF and DUAL algorithms. In Section 3 we describe DUST. In Section 4 we give the correctness analysis of DUST. In Section 5 we report the results of our experimental study. Finally, in Section 6 we give some concluding remarks and outline possible future research directions. In the appendix, we give an example of execution of DBF, DUAL and DUST, useful to appreciate the differences among the algorithms.

Preliminaries

We consider a network made of processors linked through weighted communication channels. Each processor can send messages only to its neighbors. We assume that messages are delivered to their destination within a finite delay but they might be delivered out of order. We consider an asynchronous sys-tem, that is, a sender of a message does not wait for the receiver to be ready to receive the message. Finally, there is no shared memory among the nodes of the network.

Asynchronous model. We consider an asynchronous system based on that proposed in [START_REF] Attiya | Distributed Computing[END_REF] and summarized below. The state of a processor v is the content of the data structure at processor v. The network state is the set of states of all the processors in the network plus the network topology and the channel weights. An event is the reception of a message by a processor or a change to the network state. When a processor p sends a message m to a processor q, m is stored in a buffer in q. When q reads m from its buffer and processes it, the event "reception of m" occurs. An execution is an alternate sequence (possibly infinite) of network states and events. A non negative integer number is associated to each event, the time at which that event occurs. The time is a global parameter and is not accessible to the processors of the network. The time must be non decreasing and must increase without bound if the execution is infinite. Events are ordered according to the time at which they occur. Several events can happen at the same time as long as they do not occur on the same processor. This implies that the times related to a single processor are strictly increasing.

Concurrent executions. We consider a dynamic network in which a change to the network topology or to the channel weights can occur while one or more other changes are under processing. A processor v could be affected by a subset of these changes. As a consequence, v could be involved in the executions related to such changes. Hence, according to the asynchronous model described above we need to define the notion of concurrent executions as follows. Let us consider an algorithm A that maintains some data structure on the processors of the network after a change to the network topology or to channel weights. Let c i and c j be two of such changes, we denote as: t i and t j the times at which c i and c j occur, respectively; A i and A j the executions of A related to c i and c j , respectively; and t Ai the time when A i terminates. If t i ≤ t j and t Ai ≥ t j , then A i and A j are concurrent, otherwise they are sequential.

Graph notation. We represent the network by an undirected weighted graph G = (V, E, w), where: V is a finite set of n nodes, one for each processor; E is a finite set of m edges, one for each communication channel; and w is a weight function w :

E → R + ∪ {∞}. An edge in E that links nodes u, v ∈ V is denoted as u → v or (u, v). Given v ∈ V , N (v)
denotes the set of neighbors of v and deg(v) the degree of v, which is the size of N (v). The maximum degree of the nodes in G is denoted by maxdeg. A path P in G between nodes u and v is denoted as P = u ; v. We define the length of P as the number of edges of P and denote it by ℓ(P ), and define the weight of P as the sum of the weights of the edges in P and denote it by weight(P ). A shortest path between nodes u and v is a path from u to v with the minimum weight. The distance from u to v is the weight of a shortest path from u to v, and is denoted as d(u, v). Given two nodes u, v ∈ V , the via from u to v is the set of neighbors of u that belong to a shortest path from u to v. Formally:

via(u, v) ≡ {z ∈ N (u) | d(u, v) = w(u, z) + d(z, v)}.
Given a graph G = (V, E, w), we suppose that a sequence C = (c 1 , c 2 , ..., c k ) of k operations is performed on edges (x i , y i ) ∈ E, i ∈ {1, 2, ..., k}. The operation c i either inserts a new edge in G, or deletes an edge of G, or modifies (either increases or decreases) the weight of an existing edge in G. We consider the case in which C is a sequence of weight increase and weight decrease operations, that is operation c i either increases or decreases the weight of edge (x i , y i ) by a quantity ǫ i > 0, i ∈ {1, 2, ..., k}. The extension to delete and insert operations, respectively, is straightforward: deleting an edge (x, y) is equivalent to increase w(x, y) to +∞, and inserting an edge (x, y) with weight α is equivalent to decrease w(x, y) from +∞ to α. Without loss of generality, we assume that operations in C = (c 1 , c 2 , ..., c k ) occur at times t 1 ≤ t 2 ≤ ... ≤ t k , respectively. Assuming G 0 ≡ G, we denote as G i the graph obtained by applying the operation c i to G i-1 . We denote as d i () and via i () the distance and the via over G i , 0 ≤ i ≤ k, respectively. Given a path P in G, we denote as weight i (P ) the weight of P in G i , 0 ≤ i ≤ k.

Distance vector algorithms.

Here we describe the two most popular distance vector algorithms known in the literature, the classical Bellman-Ford method (DBF) and the Diffuse Update Algorithm (DUAL).

DBF requires each node v in the network to store the last estimated distance towards any other node s ∈ V received from each neighbor u ∈ N (v), denoted as D v [u, s]. In DBF, a node v updates its estimated distance to a node s by simply executing the iteration

D v [v, s] := min u∈N (v) {w(v, u) + D v [u, s]}.
Like many distance vector algorithms, DBF suffers of the well-known countto-infinity problem, which arises when a certain kind of link failure or weight increase operation occurs in the network. Figure 1 shows a classical topology where DBF counts to infinity. In particular, the left and right sides of such a figure show a graph G before and after a weight modification on edge (s, v). Fig. 1. A graph G before and after a weight modification on the edge (s, v). the via to s for each node in G. In detail, when the weight of the edge (s, v) increases to 100, v updates its distance and via to s by setting D v [v, s] to 3 and via to {a, b}. In fact, v knows that the distance from a (and b) to s is 2, while the weight of edge (v, s) is 100. Note that, v cannot know that the path from a to s with weight 2 is that passing through edge (v, s) itself. Now, we concentrate on the operations performed by nodes a and b. When node a (b, respectively) performs the updating step, it finds out that its new via to s is b (a, respectively) and its new distance is 3. In fact, according to a's information D[v, s] = 3 and D[b, s] = 2, therefore w(a, b) + D[b, s] < w(a, v) + D[v, s]. Subsequent updating steps (but the last one) do not change the via to s of both a and b, but only the estimated distances. For each updating step the estimated distances increase by 1 (i.e., the weight of the edge (a, b)). The counting stops after a number of updating steps that depends on the new weight of the edge (s, v) and on the weight of edge (a, b). Note that, if edge (s, v) is deleted (i.e. his weight is set to ∞), the algorithm does not terminate. DUAL requires, for each node v to maintain, for each destination s a set of neighbors called the feasible successor set F[v, s], and for each u ∈ N (v), the distance D[u, s] from u to s. F[v, s] is computed using a feasibility condition involving feasible distances from each node u in N (v) to s. In detail, node u is in F[v, s] if the estimated distance D[u, s] from u to s is smaller than the estimated distance D[v, s] from v to s. If the neighbor u, through which the distance to s is minimum, is in F[v, s], then u is chosen as successor to s. If F[v, s] does not include u, then v initiates a synchronous update procedure, known as diffuse computation. Node v sends queries to all its neighbors with its distance through the current successor by using message query. From this point onwards v does not change its successor to s until the diffusing computation terminates. When a neighbor u ∈ N (v) receives a queries, it updates F[u, s]. If u has a successor to s after such update, it replies to the query by sending message reply containing its own distance to s. Otherwise, u continues the diffuse computation: it sends out queries and waits for the replies from its neighbors before replying to v's original query. When a node receives messages reply by all its neighbors, it updates its distance with the minimal value obtained by its neighbors and finishes the diffuse computation. At the end of a diffuse computation, a node sends message update containing the new computed distance to notify it to its neighbors. If there are concurrent updates, the node uses a finite state machine to process these multiple updates sequentially.

The new algorithm

In this Section we introduce DUST, our new solution for the concurrent update of distributed all-pairs shortest paths in dynamic networks. In detail, in Section 3.1, we define the data structure per node needed by DUST and give the pseudo-code of the algorithm; in Section 3.2, we outline the main ideas of the behavior of DUST by giving two examples of executions; in Section 3.3, we compare DUST with respect to DBF, DUAL, INC and DEC in terms of number of messages sent and space occupancy per node. The correctness of DUST is given in Section 4.

Data structures and pseudo-code

Given G = (V, E, w), we assume that each node of G knows the identity of every other node of G, the identity of all its neighbors and the weights of the edges incident to it. The information on the shortest paths in G are stored in a data structure called routing table RT distributed over all nodes. Each node v maintains its own routing table RT v [•], that has one entry RT v [s], for each s ∈ V . The entry RT v [s] consists of two fields: Algorithm DUST is reported in Figure 3, 4 and 5, and is described in what follows with respect to a source s ∈ V . Before the algorithm starts, we assume that, for each v, s ∈ V and for each t < t 1 , D t [v, s] and VIA t [v, s] are correct, that is D t [v, s] = d 0 (v, s) and VIA t [v, s] = via 0 (v, s). The algorithm starts at each t i , i ∈ {1, 2, ..., k}. The event related to operation c i on edge (x i , y i ) is detected only by nodes x i and y i . As a consequence, if c i is a weight increase (weight decrease) operation, x i sends the message increase(x i , s) (decrease(x i , s, D ti [x i , s])) to y i and y i sends the increase(y i , s) (decrease(y i , s, D ti [y i , s])) message to x i , for each s ∈ V . Note that message decrease includes information about the distance from y i to s, while message increase does not. In the case of a weight increase, in fact, such distance will be possibly obtained by x i in the subsequent rebuild-table phase (see the following description).

-RT v [s].D, the estimated distance between nodes v and s in G; -RT v [s].VIA ≡ {u ∈ N (v) | RT v [s].D = w(v, u) + RT u [s].D},
If a node v receives the message decrease(u, s, D[u, s]), then it performs Procedure Decrease in Figure 3. Basically, Decrease performs a relaxation

Event: node v receives the message decrease(u, s, D[u, s]) from u Procedure Decrease 1. if w(v, u) + D[u, s] < D[v, s] then 2.
begin Lines 2-7: phase improve-table 3.

D[v, s] := w(v, u) + D[u, s] 4.
VIA[v, s] := {u} 5.

for each

v i ∈ N (v) do 6. send decrease(v, s, D[v, s]) to v i 7. end 8. else 9. if D[v, s] = w(v, u) + D[u, s] then 10.
VIA[v, s] := VIA[v, s] ∪ {u} Line 10: phase extend-via Fig. 3.

Event: node v receives the message increase(u, s) from u Procedure Increase 1. if u ∈ VIA[v, s] then 2. begin 3. VIA[v, s] := VIA[v, s] \ {u} Line 3: phase reduce-via 4.
if VIA[v, s] ≡ ∅ then 5.

begin Lines 5-17: phase rebuild-table 6.

old distance

:= D[v, s] 7.
for each

v i ∈ N (v) do 8. receive D[v i , s] by sending get-dist(v, s) to v i 9. D[v, s] := min v i ∈N (v) {w(v, v i ) + D[v i , s]} 10. VIA[v, s] := {v i ∈ N (v)|w(v, v i ) + D[v i , s] = D[v, s]} 11.
for each

v i ∈ N (v) do 12. begin 13. if D[v, s] > old distance then 14. send increase(v, s) to v i 15. send decrease(v, s, D[v, s]) to v i crh2 16. end 17. end 18.
end

Fig. 4. of edge (u, v). In particular, if w(v, u) + D[u, s] < D[v, s] (Line 1
), then v needs to update its estimated distance to s. To this aim, v performs phase improve-table, that updates D[v, s] and VIA[v, s] (Lines 3-4), and propagates the updated values to the nodes in

N (v) (Line 6). Otherwise, if w(v, u) + D[u, s] = D[v, s] (Line 9
), then u is a new estimated via for v wrt destination s, and hence v performs phase extend-via, that simply adds u to VIA[v, s] (Line 10). If a node v receives the message increase(u, s), then it performs Procedure Increase in Figure 4. While performing Increase, v simply checks whether the message comes from a node in VIA[v, s] (Line 1). In the affirmative case, v needs to remove u from VIA[v, s]. To this aim, v performs phase reduce-via (Line 3). As a consequence of this deletion, VIA[v, s] may become empty. In

Event: node v i receives the message get-dist(v, s) from v Procedure Send-Dist 1. if (VIA[v i , s] ≡ {v}) crt1 or (v i is performing rebuild-table or improve-table wrt destination s) crt2 2. then send ∞ to v crh1 3. else send D[v i , s] to v Fig. 5.
this case, v performs phase rebuild-table, whose purpose is to compute the new estimated distance and via of v to s. To do this, v asks to each node v i ∈ N (v) for its current estimated distance, by sending message get-dist(v, s) to v i (Lines 7-8). When v i receives message get-dist(v, s) by v, it performs Procedure Send-Dist in Figure 5. While performing Send-Dist, v i basically sends D[v i , s] to v, unless one of the following two conditions holds:

1. VIA[v i , s] ≡ {v}; 2. v i is performing rebuild-table or improve-table wrt destination s.
The test of these two conditions is part of our strategy to reduce the cases in which the count-to-infinity phenomenon appears. The test is performed at Line 1 of Send-Dist, where the conditions are labeled as crt 1 and crt 2 , respectively (the acronym stands for Count Reducing Test). If crt 1 or crt 2 are true, then v i sends ∞ to v. This action is performed at Line 2, and is labeled as crh 1 (the acronym stands for Count Reducing Heuristic). More details on the strategy for the reduction of the count-to-infinity phenomenon are given in Section 3.3.

Once node v has received the answers to the get-dist messages by all its neighbors, it computes the new estimated distance and via to s (Lines 9-10). Now, if the estimated distance has been increased, v sends an increase message to its neighbors (Line 14). In any case, v sends to its neighbors the message decrease (Line 15), to communicate them D[v, s]. This action, that we call crh 2 , is also part of our strategy to reduce the count-to-infinity phenomenon. In fact, at some point, as a consequence of crh 1 , v could have sent ∞ to a neighbor v j . Then, v j receives the message sent by v at Line 15, and it performs Procedure Decrease to check whether D[v, s] can determine an improvement to the value of D[v j , s].

Behavior of DUST

In what follows, we describe the behavior of DUST by giving two examples which focus on the steps performed by DUST when a sequence of only weight decrease or only weight increase operations occur. The aim of the first example is to show how procedure Decrease behaves, while the aim of the second example is to show how procedure Increase behaves and how the count prevention heuristics work. The steps performed by DUST when sequences of mixed increase/decrease operations occur are a combination of those performed in the previous two cases.

s u 1 v via i (v, s) via j (v, s) ≡ via k (v, s) z 3 z 1 z 2 u 2 y j x j y i x i via j (y j , s) ≡ via k (y j , s) via i (y i , s) ≡ via k (y i , s)
In general, given a pair of nodes s, v ∈ V , at the end of the update sequence C = (c 1 , c 2 , ..., c k ), that is at time t k , three cases may arise:

Case 1. The distance from v to s decreases, that is d 0 (v, s) > d k (v, s); Case 2. The distance from v to s increases, that is d 0 (v, s) < d k (v, s); Case 3. The distance from v to s does not change, that is d 0 (v, s) = d k (v, s).
Notice that, in each of the above cases, the distance between v and s can change (increase or decrease) many times between t 0 and t k . We analyze the three cases separately.

Case 1. d 0 (v, s) > d k (v, s). A possible scenario for the shortest paths from v to s in G k is shown in Figure 6, where the edges are represented as straight lines while the paths are represented as curves. There are two weight decrease operations c i and c j , occurring at times t i and t j , t i < t j , that decrease the weights of edges (x i , y i ) and (x j , y j ), respectively. As a consequence of these operations, the distance from v to s decreases and the edges (x i , y i ) and (x j , y j ) belong to the shortest paths from v to s in G j . Here, we assume that c i and c j are the only operations in C that affect the shortest paths from v to s. This implies that via j (v, s) ≡ via k (v, s) and

d i (v, s) = d j (v, s) = d k (v, s). In detail, the shortest path from v to s in G i is the path P i = v → u 1 ; y i → x i ; s and via i (v, s) ≡ {u 1 },
while the shortest paths from v to s in G j are the paths P i and P j = v → u 2 ; y j → x j ; s, and via j (v, s) ≡ via k (v, s) ≡ {u 1 , u 2 }. We show that the algorithm starts by updating the routing table of nodes y i and y j , and then it updates the routing tables of the nodes in the sub-paths v → u 1 ; y i and v → u 2 ; y j of the shortest paths P i and P j , respectively. When, at time t i , the weight decrease operation c i occurs, x i and y i send their estimated distances to each other. When x i receives decrease(y i , s, D ti [y i , s]) by y i , it executes procedure Decrease in Figure 3, which first checks whether it is necessary to start the algorithm (see Line 1). In the affirmative case, x i updates D[x i , s] and VIA[x i , s] (see Lines 3-4) at a certain time t and sends the message decrease(x i , s, D t [x i , s]) to its neighbors (Line 6). The behavior of y i (when y i receives the message decrease(x i , s, D ti [x i , s])) is symmetric. At most one between x i and y i will propagate the decrease messages. In fact, if we assume, without loss of generality, that D ti [x i , s] ≤ D ti [y i , s], then the test performed by x i at Line 1 of Procedure Decrease is false. Thus, x i does not need to propagate the decrease message to its neighbors. Conversely, under the same assumptions, y i may improve its distance from s. In this case y i updates its routing table at a certain time t and sends the message decrease(y i , s, D t [y i , s]) to its neighbors. If we assume that D tj [x j , s] ≤ D tj [y j , s], the behavior of nodes x j and y j at time t j is analogous to that of nodes x i and y i at time t i .

The decrease messages sent by y i (y j respectively) will update the values of D[u, s] and VIA[u, s], for each node u in the subpath from y i (y j respectively) to v of P i (P j respectively). Let us denote as m i and m j the decrease messages received by v, and propagated along paths P i and P j respectively. Further, let us denote as t mi and t mj the time when v receives m i and m j respectively. Note that, in an asynchronous system, even if t i < t j , nothing is known about the ordering of t mi and t mj . Let us assume that t mi < t mj , the case where t mi > t mj is symmetric. When, at time t mi , v receives m i , it performs improve-table phase of procedure Decrease and then, it updates

D[v, s] and VIA[v, s] by setting D[v, s] = w(u, v) + d i (u, s) = d k (v, s) and VIA[v, s] ≡ {u 1 } ≡ via i (v, s)
. At time t mj , v receives m j and performs extend-via phase of procedure Decrease and then, it adds

u 2 to VIA[v, s] setting VIA[v, s] ≡ {u 1 , u 2 } ≡ via j (v, s) ≡ via k (v, s). Finally, v sends the message decrease(v, s, D k [v, s]) to nodes in N (v)
. At this point, node v has correctly computed its current distance and via to s, and it has propagated this information to its neighbors.

Case 2. d 0 (v, s) < d k (v, s). A possible scenario for the shortest paths from v to s in G 0 is represented in Figure 7. In this figure, we consider only weight increase operations that occur on edges (x i1 , y i1 ), (x i2 , y i2 ), (x j1 , y j1 ) and (x j2 , y j2 ). Note that, via 0 (y i1 , s) ≡ {x i1 , x i2 } and via 0 (y j1 , s) ≡ {u 4 , x j1 , x j2 }.

Since d 0 (v, s) < d k (v, s), each shortest path from v to s in G 0 contains an edge that has been increased by a weight increase operation. Moreover, there exist nodes y i such that, for each x i ∈ via 0 (y j1 , s), edge (x i , y i ) has been increased. We call the set of such nodes Y s . For example, in the scenario of Figure 7, Y s ≡ {y i1 } ≡ {y i2 }.

In order to update its estimated distance and via to s, node v has to perform Procedure Increase. In particular, v has to perform reduce-via phase to remove from VIA[v, s] nodes that no longer belong to via(v, s). Moreover, if VIA[v, s] becomes empty, v has to perform rebuild-table phase to update its routing table and propagate the increase messages. In what follows we describe how nodes that increase their distance to s at time t k perform Procedure Increase. First, (I) we show that nodes in Y s starts the updating phase by performing rebuild-table phase; then, (II) we show that node v is reached by the algorithm and it also performs rebuild-table phase; finally, (III) we show how v updates its routing table. (I) For each i ∈ {1, 2, . . . , k}, such that y i ∈ Y s , x i ∈ via 0 (y i , s) and c i is a weight increase operation, at time t i , nodes x i and y i send an increase message to each other1 . Each time that y i receives an increase message m, it removes from VIA[y i , s] the node of via 0 (y i , s) that sent m (see phase reduce-via). Hence, if t ∅ (y i , s) is the time when y i has received all the increase messages coming from all the nodes in via 0 (y i , s), then VIA t ∅ (yi,s) [y i , s] ≡ ∅. At time t ∅ (y i , s), y i performs test at Line 4 of Procedure Increase, and the test returns true. Hence, y i performs rebuild-table phase which updates the routing table of y i and propagates the increase messages. More details on this procedure are discussed later when we analyze the behavior of a generic node v. For example, in Figure 7, node y i1 sends an increase message to each node in N (y i1 ) and hence, to neighbors of y i1 in the shortest paths from v to s in G 0 that contain y i1 .

y j 1 ≡ y j 2 x j 2 u 4 x j 1 via 0 (y j 1 , s) u 1 v z 1 z 3 z 2 u 2 u 3 via 0 (v, s) s x i 1 x i 2 via 0 (y i 1 , s) y i 1 ≡ y i 2
(II) It can been shown by induction that each node in the shortest paths from y i1 to v and from y j1 to v has the same behavior of y i1 , that is it performs rebuild-table phase and sends increase messages to its neighbors. It follows that node v is eventually reached by increase messages sent by nodes in via 0 (v, s).

(III) Now we can analyze in detail the execution of rebuild-table phase by a generic node v at a certain time t. In order to update D[v, s] and VIA[v, s], v needs to know the estimated distances to s of each node in N (v), that is, D t [v i , s], for each v i ∈ N (v). In Figure 7, node v needs the estimated distance of each z i and u j , i, j ∈ {1, 2, 3}. To this aim, v sends the message get-dist(v, s) to v i , for each v i ∈ N (v) (Line 8 of Procedure Increase). When, at a time t vi , v i receives get-dist(v, s), it performs Procedure Send-Dist. Note that, in our model, multiple increase and decrease messages on a single node are processed one by one, while get-dist messages are processed immediately. To analyze the behavior of nodes in N (v) when they receive get-dist messages, let us assume that, in the scenario of Figure 7, the following conditions hold: will perform rebuild-table phase and then it will send a decrease message to v containing the current estimated distance from z 1 to s, by performing crh 2 . At this point, node v has received all the information needed to correctly compute its current distance and via to s, and to propagate them to its neighbors.

-Node z 1 satisfies crt 1 , that is at time t z1 , VIA tz 1 [z 1 , s] ≡ {v}; -Node z 2 satisfies crt 2 ,
Case 3. d 0 (v, s) = d k (v, s). Two cases may occur:

1. if d i-1 (v, s) = d i (v, s), for each i ∈ {1, 2, . . . , k}, then the shortest paths from v to s in G k are the same of G 0 , that is v never updates RT v [s]. 2. If there exists i ∈ {1, 2, . . . , k} such that d i-1 (v, s) = d i (v, s), then there ex- ists j ∈ {1, 2, . . . , k} such that if d i-1 (v, s) < d i (v, s) (d i-1 (v, s) > d i (v, s), respectively), then d j-1 (v, s) > d j (v, s) (d j-1 (v, s) < d j (v, s), respec- tively).
In these cases, the algorithm propagates messages decrease and increase as in Cases 1 and 2.

In any case, v has correctly stored its current distance and via to s, and, possibly, it has propagated this information to its neighbors.

Comparison to existing algorithms

In what follows, we compare DUST with DBF, DUAL, INC and DEC in terms of number of messages sent and space occupancy per node. Like many other distance vector algorithms, both DBF and DUST suffer of the count-to-infinity problem and hence the number of messages sent cannot be asymptotically bounded by a function of the size of the graph. However, DUST has been designed to heuristically reduce the number of cases where it counts to infinity. In fact, let us consider again the example of Figure 1 where DBF counts to infinity. In Figure 8 edge (s, v), they perform Procedure Increase with respect to source s. In particular, s does not perform rebuild-table phase as VIA[s, s] = ∅, while v does. When v gets the estimated distances to s from its neighbors (Line 8 of Procedure Increase), it receives ∞ from both a and b. This is due to the fact that since test crt 1 returns true, a and b apply heuristic crh 1 . At the end of these execution, v correctly updates its routing table and sends messages increase and decrease to each neighbor. It is easy to verify that, when s receives the decrease and increase messages from v, it does not perform any local data modification. In contrast, both a and b perform Procedure Increase when they receive the increase message from v. In this case, a and b send ∞ (as their estimated distance to s) to each other in response to the get-dist message. This is due to the fact that the algorithm applies again crh 1 but, in this case, crh 1 is due to test crt 2 , which returns true. Hence, both a and b correctly update their routing tables by using messages sent by v. Subsequent messages sent by a and b do not produce further local data modification.

In the previous example, there are nodes that apply action crh 2 . However, this action is never effective since the conditions of Lines 1 and 9 of Decrease are always false. In what follows, we describe how to modify the graph G in Figure 1 Regarding the comparison with DUAL, as already observed, DUAL and DUST asymptotically requires the same space per node in the worst case, that is O(n • maxdeg). However, in what follows we observe that in practice the memory requirement of DUST is smaller than that of DUAL. DUAL requires a node v to store, for each destination s, the estimated distance D[u, s] from each of its neighbors u, hence the space requirement of dual is exactly O(n • deg(v)). DUST only needs the estimated distance of v to s and the set VIA[v, s]. In the worst case, VIA[v, s] can have deg(v) elements, but in practice this happens rarely (indeed, as we will experimentally show, it is not common to have more than one node in such set). It hence follows that the practical space requirements of DUST do not depend on the node degree.

In contrast to the space occupancy, the node degree affects the performances of DUST in terms of the number of messages sent. In fact, as DUST does not store the estimated distances of its neighbors, it needs to ask for them by sending get-dist message when they are needed. Hence, the number of get-dist messages sent by a node is proportional to the node degree. For this reason, in general DUAL sends a number of messages which is smaller than that of DUST. However, in real-world graphs the average node degree is small and then the number of get-dist messages sent is also small. In fact, we will experimentally show that in real-world graphs DUST sends less messages than DUAL.

Regarding the comparison with DEC and INC, we stress that such solutions are only incremental and decremental, respectively, and hence cannot cope with fully dynamic sequences of updates as the two algorithms use different data structure. In particular, INC has an optimal space occupancy per node as it stores only the routing table and it has a message complexity that is a factor maxdeg far from the optimal one. Such good theoretical bound of INC are due to the hypothesis that only weight decrease operations are assumed to occur in the network. In fact, INC is able to discard many messages thanks to a filtering condition which cannot be used in case of weight increase operations. DEC uses the same data structure of DUST and counts to infinity. However, DUST, in addition to being fully dynamic, is able to reduce the cases where the count-to-infinity occurs in sequences of weight increase operations, thanks to heuristic crh 2 which is not used in DEC.

Correctness

In this section, we prove the correctness of DUST. Let G be a graph and C = (c 1 , c 2 , ..., c k ) a sequence of weight increase and weight decrease operations occurring on G at times t 1 ≤ t 2 ≤ ... ≤ t k and generating graphs G 1 , G 2 , . . . G k , respectively. We show that, for any pair of nodes v and s, there exists a time t F such that for each time t ≥ t F the routing table of v with respect to s is that of G k , formally:

D t [v, s] = d k (v, s) and VIA t [v, s] ≡ via k (v, s).
Such statement is proven in Theorem 1, the following lemmata are needed for the proof.

Lemma 1 Given v, s in G such that d 0 (v, s) < d k (v, s)
, there exists a node y such that, for each x ∈ via 0 (y, s), w(x, y) has been increased by an operation in C, and d 0 (y, s) < d k (y, s).

Proof. By contradiction, let us suppose that, for each y ∈ {y 1 , y 2 , . . . , y k }, either there exists z ∈ via 0 (y, s) such that w(z, y) has not been increased by any weight increase operation, or d 0 (y, s) ≥ d k (y, s). This implies that nodes of G can only decrease the distance to s as a consequence of the weight changes c 1 , c 2 , ..., c k . Hence, d 0 (v, s) ≥ d k (v, s), which is a contradiction. 2

Let Y s be the set of nodes y satisfying Lemma 1 with respect to destination s. that is the estimated weight of P is smaller or equal to d 0 (y, s). But, since by hypothesis d 0 (y, s) < d k (y, s), the actual weight of P in G k is such that weight k (P ) > d 0 (y, s). Hence, in any case, P contains an edge whose weight has been increased by another operation in C, that is P has the following structure P = y → u ; ȳ → x ; s where edge (x, ȳ) is the edge whose weight has been increased. Since d 0 (y, s) < d k (y, s), then all paths having the following structure

Lemma 2 Given v, s in G such that d 0 (v, s) < d k (v,
P ′ = y ; ȳ ; s
where y ; ȳ is the subpath of P from y to ȳ, satisfy weight k (P ′ ) > d 0 (y, s). It follows that, d 0 (ȳ, s) < d k (ȳ, s). The set via 0 (ȳ, s) consists of two disjoint subsets, X(ȳ, s) ≡ {x | w(x, ȳ) has been increased by an operation in C} and Ū (ȳ, s) ≡ via 0 (ȳ, s) \ X(ȳ, s), where X(ȳ, s) ≡ ∅, since x ∈ X. If Ū (ȳ, s) ≡ ∅, then ȳ ∈ Y s . If Ū (ȳ, s) ≡ ∅, then, for each node ū ∈ Ū (ȳ, s), there exists a path from ū to s that contains a node in Y s . In any case, there exists a path from y to s having the following structure

P 0 = y → u ; y i1 → x i1 ; s
where edge (x i1 , y i1 ) is an edge whose weight has been increased. Furthermore y i1 ∈ Y s , hence the same arguments can be used to show that there exists a path:

P 1 = y i1 → u i1 ; y i2 → x i2 ; s
where the edge (x i2 , y i2 ) is involved in a weight increase operation, y i2 ∈ Y s and Dt

i 1 [y i1 , s] ≥ w(y i1 , u i1 ) + D tu i 1 [u i1 , s], t ui 1 < t yi 1 .
In general, for each y j ∈ Y s there exists a path: P j = y j → u j ; y j+1 → x j+1 ; s where the edge (x j+1 , y j+1 ) is involved in a weight increase operation, y j+1 ∈ Y s and D tj [y j , s] ≥ w(y j , u j ) + D tu j [u j , s], t uj < t j . That is, since |Y s | < ∞, there exists a cycle:

y → u ; y i1 → u i1 ; y i2 → u i2 ; ... ; y i h → u i h ; y such that: Dt i 0 [y, s] ≥ w(y, u) + D tu [u, s] > D tu [u, s] ≥ Dt i 1 [y i1 , s] ≥ w(y i1 , u i1 ) + D tu i 1 [u i1 , s] > D tu i 1 [u i1 , s] ≥ ... Dt i h [y i h , s] ≥ w(y i h , u i h ) + D tu i h [u i h , s] > D tu i h [u i h , s] ≥ Dt′ i 0 [y, s],
where ti0

> t u > ti1 > t ui 1 ... > ti h > t ui h > t′ i0 , that is Dt i 0 [y, s] > Dt′ i 0 [y, s] with ti0 > t′
i0 that is a contradiction. Hence there exists y ∈ Y s and a time t ∅ (y, s) such that VIA t ∅ (y,s) [y, s] ≡ ∅.

2

Let us denote as Y ′ s ⊆ Y s the set of nodes satisfying Lemma 2 with respect to destination s. The next Lemma states that condition in Line 13 of Procedure Increase is true for each y in Y ′ s , and hence that y sends increase messages to nodes in N (y).

Lemma 3 Given v, s in G such that d 0 (v, s) < d k (v, s), for each y ∈ Y ′
s , y sends an increase message to each node in N (y).

Proof. Each node y in Y ′

s performs rebuild-table phase at least once at time t ∅ (y, s). By contradiction, let us suppose that each execution of rebuild-table phase does not send any increase message, that is the condition in line 13 of procedure Increase is always false, for each y ∈ Y ′ s . Hence, for each y ∈ Y ′ s and for each t ∅ (y, s), if we denote as t ′ y the time when y performs line 9 of procedure Increase, there exists a node u in N (y) and a time t u < t ′ y such that:

D t ′ y [y, s] = w(y, u) + D tu [u, s] ≤ D t ∅ (y,s) [y, s]
. Let P u be the path from y to s containing u whose estimated weight is w(y, u)+ D tu [u, s]. The same arguments used in the proof of Lemma 2 can be used to prove that P u contains an edge whose weight has been increased by an operation in C and to derive a contradiction.

2

The next Lemma states that each node v such that d 0 (v, s) < d k (v, s) has the same behavior of nodes in Y ′ s that is, v performs rebuild-table phase and sends increase message to each node in N (v).

Lemma 4 Given v, s in G such that d 0 (v, s) < d k (v, s), v performs rebuild-table phase wrt source s and it sends an increase message to each node in N (v).

Proof. We denote as:

P s (v) = {P = v ; y | y ∈ Y ′ s ∧ ∃ P ′ = v ; s : P ⊆ P ′ } L s (v) = max{ℓ(P ) | P ∈ P s (v)} the proof is by induction on L s (v). Inductive basis (L s (v) = 0): a node v is such that L s (v) = 0 and d 0 (v, s) < d k (v, s) if and only if v ∈ Y ′
s . By Lemma 2, v performs rebuild-table phase and by Lemma 3, it sends an increase message to each node in N (v). Inductive step: the inductive hypothesis is: each node v such that L s (v) ≤ l-1 and d 0 (v, s) < d k (v, s) performs rebuild-table phase and sends and increase message to each node in N (v).

Let v be a node such that L s (v) = l and d 0 (v, s) < d k (v, s) and u be a node in N (v) such that:

D tv [v, s] = w(v, u) + D tu [u, s] u ∈ VIA tv [v, s]
at certain times t v and t u such that t u < t v .

Two cases may occur:

d 0 (u, s) < d k (u, s): by inductive hypothesis, u sends an increase message to v. -d 0 (u, s) ≥ d k (u, s): let P s (v, u, t v ) be the set of estimated shortest paths from v to s via u at time t v . Since d 0 (v, s) < d k (v, s), each path P in P s (v, u, t v ) contains a node y P ∈ Y s . For each P ∈ P s (v, u, t v ), y P is such that L s (y P ) ≤ l -1, then y P sends an increase message to each node in N (y P ). Thus the message is propagated in each path in P s (v, u, t v ). Hence u sends an increase message to v.

In any case, each node in VIA tv [v, s] sends an increase message to v and then there exists a time t when VIA t [v, s] ≡ ∅ and v performs rebuild-table phase.

The same arguments can be used to show that v sends an increase message to each node in N (v).

2

In the remainder we will use the following further notation for each pair of nodes v and s: Lemma 5 For each pair of nodes v and s and for any time

-Exe l (v,
t ≥ t ′ l (v, s), D t [v, s] ≥ d k (v, s).
Proof. Two cases may occur:

1. v never updates D[v, s].
For any time t, we have:

D t [v, s] = d 0 (v, s).
As v never updates D[v, s], it never performs rebuild-table and it never sends increase messages, hence, by Lemma 4, d 0 (v, s) ≥ d k (v, s). Then, for each time t:

D t [v, s] ≥ d k (v, s).

v updates D[v, s] at least once. By contradiction, let us suppose that v is

the first node failing to update its routing table and let t v ≥ t ′ l (v, s) be the smallest time such that

D tv [v, s] < d k (v, s).
(1)

For each z ∈ VIA tv [v, s], D tv [v, s] = w(v, z) + D tz [z, s], t z < t v . If there exists a node z ∈ VIA tv [v, s] such that t z ≥ t ′ l (z, s), since v is the first node to fail, then D tz [z, s] ≥ d k (z, s). Thus D tv [v, s] = w(v, z) + D tz [z, s] ≥ w(v, z) + d k (z, s) ≥ d k (v,
(z, v). Let t max = max{t m ′ (z, v) | z ∈ VIA tv [v, s] ∪ Ext(v, s)}.
Informally, t max is the time when v receives the last increase message from nodes in VIA tv [v, s]∪ Ext(v, s). It follows that, at time t max , v performs Procedure Increase and tests at Lines 1 and 4 return true. Then, v performs phase rebuild-table

at time t max > t v ≥ t l (v, s). Furthermore, since each z ∈ VIA tv [v, s] ∪ Ext(v, s) increases the value of D[z, s], v increases D[v, s] after the time t ′ l (v, s)
, a contradiction with respect to the definition of t ′ l (v, s).

2

Corollary 1 For each pair of nodes v and s and for any time t ≥ t l (v, s),

D t [v, s] ≥ d k (v, s).
Proof. Since t l (v, s) ≥ t ′ l (v, s), the statement follows directly by Lemma 5 2

Remark 1 Let v be a node in V and z be a node in N (v). If there exists a pair of times t ′ , t ′′ such that:

-t ′ ≤ t ′′ ; -for each t z , t ′ ≤ t z ≤ t ′′ , D tz [z, s] = d where d is a certain real value; -at time t v , t ′ ≤ t v ≤ t ′′ , D tv [v, s] ≤ w(v, z) + d.
Then, for each time

t, t v ≤ t ≤ t ′′ , D t [v, s] ≤ w(v, z) + d.
Theorem 1 There exists t F such that, for each pair of nodes v, s ∈ V , and for each time

t ≥ t F , D t [v, s] = d k (v, s) and VIA t [v, s] ≡ via k (v, s).
Proof. The correctness of the algorithm is shown with respect to a fixed source s. The correctness for all pairs of nodes is a straightforward consequence. In fact, since procedures Decrease, Increase and Send-Dist always refer to the record of the routing table related to a single source, then two executions of the algorithm related to two different sources cannot access the same record of the routing table.

If the statement is true for nodes v and s, then we denote as t F (v, s) the time when the statement occurs for v and s. If there exists t F (v, s) for each v, s ∈ V , then t F = max v∈V (t F (v, s)). Now we show that t F (v, s) exists for a generic pair (v, s). We need the following definitions:

P s (v) = {P = v ; s | P is a shortest path in G k } L s (v) = max{ℓ(P ) | P ∈ P s (v)}
the proof is by induction on L s (v). Inductive basis (L s (v) = 0): the unique node such that L s (v) = 0 is s. For any time t ≤ t 1 , we have:

D t [s, s] = d 0 (s, s) = 0 VIA t [s, s] ≡ via 0 (s, s) ≡ ∅.
If s never changes RT s [s], then t F (s, s) = t 1 . Hence we have to show that s does not perform any of the following phases: improve-table, extend-via, reduce-via and rebuild-table. Node s can perform:

improve-table or extend-via as a consequence of a decrease message; -reduce-via and rebuild-table as a consequence of an increase message. Let t m be the time when s receives the first decrease or increase message m.

if m = decrease(z, s, D tz [z, s]), where z ∈ N (s) and t z < t m , then, since D tm [s, s] = 0 and w(s, z) > 0, the condition in lines 1 and 9 of procedure Decrease are false. Thus v does not perform neither improve-

D t1 [v, s] = d 0 (v, s) ≤ d k (v, s) = w(v, u) + d k (u, s)
and, since, for each time t ≥ t 1 , D t [u, s] does not change, by Remark 1, we have:

D t [v, s] ≤ w(v, u) + d k (u, s) = d k (v, s).
Furthermore, by Corollary 1, for each t ≥ t l (v, s):

D t [v, s] ≥ d k (v, s). Thus t D (v, s) = max{t 1 , t l (v, s)}.
-If at least a node in via k (v, s) sends a message to v, then, let u 1 , u 2 , ..., u h be the nodes in via k (v, s) that send a message to v. By inductive hypothesis, each u i sends to v at least one of the messages: increase(u i , s) or decrease(u i , s, d k (u i , s)). Let m ui be the last of such messages sent by u i and let m = increase(u, s) or m = decrease(u, s, d k (u, s)) be the first message among m ui , 1 ≤ i ≤ h, received by v. When v receives m, it performs the procedure Increase or Decrease and, as a consequence, at time t m stores:

D tm [v, s] ≤ w(v, u) + d k (u, s).
Since m is the last message sent by u, for each time t ≥ t m , D t [u, s] does not change and then, by Remark 1, we have:

D t [v, s] ≤ w(v, u) + d k (u, s) = d k (v, s).
Furthermore, by Corollary 1, for each t ≥ t l (v, s):

D t [v, s] ≥ d k (v, s)
.

Thus: t D (v, s) = max{t m , t l (v, s)}.
Now we show that there exists a time t VIA (v, s) such that, for each

t ≥ t VIA (v, s), VIA t [v, s] ≡ via k (v, s).
Let u be a node in via k (v, s) and t mu be the time when v receives the last message m u giving a correct estimated distance from u to s or a time before t 1 if u never updates D[u, s]. Now we analyze different cases according to t mu . For each of such cases we show that u is added to VIA[v, s] and is never removed anymore.

t mu > t l (v, s). We now show that m u = decrease(u, s, d k (u, s)). By contradiction, let us suppose that m u = increase(u, s). Then, since u sends an increase message only if test at Line 13 of procedure Decrease is true, there exists a time t such that, for each t, t s) and t is the smallest time that fulfill this condition. For each of the following cases we obtain a contradiction: -if t < t l (v, s), then by Remark 1:

1 ≤ t ≤ t < t l (v, s), D t [u, s] < d k (u,
D t l (v,s) [v, s] ≤ w(v, u) + D t[u, s] < w(v, u) + d k (u, s) = d k (v, s)
that is a contradiction with respect to Corollary 1.

-If t ≥ t l (v, s), then at time t, u sends the message decrease(u, s, D t[u, s])
that is received by v at time t > t. At time t, we have:

Dt[v, s] = d k (v, s) = w(v, u) + d k (u, s) < w(v, u) + D t[u, s].
Hence the condition in line 1 of procedure Decrease is true and v performs improve-table phase at a time greater then t l (v, s) that is a contradiction with respect to the definition of t l (v, s).

Hence, m u = decrease(u, s, d k (u, s)). Since t mu > t l (v, s), then D tm u [v, s] = d k (v, s) = w(v, u) + d k (u, s).
Hence, when v receives m u , the condition in line 9 of procedure Decrease is true and then v adds u to VIA[v, s] at time t u . Since m u is the last message sent by u to v and, at time t > t u , v has performed Exe l (v, s), u will not be removed from VIA[v, s]. -t mu < t l (v, s). We now show that Exe l (v, s) performs phase rebuild-table.

By Remark 1, we have that, for each t ≥ t mu ,

D t [v, s] ≤ w(v, u) + d k (u, s) = d k (v, s).
By contradiction, let us suppose that Exe l (v, s) performs improve-table as a consequence of a decrease message received at time t ≥ t mu . Then the condition at Line 1 of procedure Decrease is true and, at time t l (v, s), v assigns a value of D[v, s] such that:

D t l (v,s) [v, s] < D t[v, s] ≤ d k (v, s)
that is a contradiction with respect to Corollary 1. Hence Exe l (v, s) performs phase rebuild-table. Since t mu < t l (v, s), Dt[u, s] = d k (u, s), where t is the time when, during Exe l (v, s), v receives D[u, s] as an answer to the message get-dist(v, s) sent to u. Hence v adds u to VIA[v, s] at time t u = t l (v, s). Since m u is the last message sent by u to v and, at time t > t u , v has performed Exe l (v, s), u will not be removed from VIA[v, s]. -t mu = t l (v, s). Since two events cannot occur to the same processor at the same time, we have t mu = t l (v, s) < t 1 that is, neither u nor v changes its distance estimate to s and u does not sends any message to v. Thus u ∈ via 0 (v, s) and v never removes u from VIA[v, s]. In this case we denote

t u = t 1 . Thus for each time t ≥ max{t u | u ∈ via k (v, s)}, each node in via k (u, s) belongs to VIA t [u, s].
There may exist a node z in

N (v) \ via k (v, s) that belongs to VIA t [u, s] for a certain time t. Since z / ∈ via k (v, s), then d k (v, s) < w(v, s) + d k (z, s). Hence v added z to VIA t [v, s] as a consequence of an underestimated value of D[z, s].
By Corollary 1, at time t l (z, s), z will increase its estimated distance and send to v an increase message m z = increase(z, s). As a consequence, v will perform phase reduce-via at time t z . Thus:

t VIA (v, s) = max{{t u | u ∈ via k (v, s)} ∪ {t z | z ∈ N (v) \ via k (v, s)}}.
Hence for a generic node v we have:

t F (v, s) = max{t D (v, s), t VIA (v, s)}. 2

Experimental analysis

In this section, we report the results of our experimental study on the performance of DUST against DBF, DUAL, INC and DEC. In detail, we first describe the implementation platform and the executed tests, and then we analyze the results of our study.

Experimental environment. The experiments have been carried out on a workstation equipped with a 2.66 GHz processor (Intel Core2 Duo E6700 Box) and 8Gb RAM. The experiments consist of simulations within the OMNeT++ environment, version 4.0p1 [START_REF]Omnet++: the discrete event simulation environment[END_REF]. OMNeT++ is an object-oriented modular discrete event network simulator, useful to model protocols, communication networks, multiprocessors and other distributed systems. An OMNeT++ model consists of hierarchically nested modules, that communicate through message passing. In our model, we defined a basic module node to represent a node in the network. A node v has a communication gate with each node in N (v).

Each node can send messages to a destination node through a channel which is a module that connects gates of different nodes (both gate and channel are OMNeT++ predefined modules). A channel connects exactly two gates and represents an edge between two nodes. We associate two parameters per channel: a weight and a delay. The former represents the weight of the edge in the graph, and the latter simulates a finite but not null transmission time.

Executed tests. For our experiments we used both real-world and artificial instances of the problem. In detail, we used the CAIDA IPv4 topology dataset [START_REF] Hyun | The CAIDA IPv4 routed/24 topology dataset[END_REF] and two classes of random graphs generated, respectively, by the Barabási-Albert algorithm [START_REF] Albert | Emergence of scaling in random networks[END_REF] and the Erdős-Rényi algorithm [START_REF] Bollobás | Random Graphs[END_REF]. CAIDA (Cooperative Association for Internet Data Analysis) is an association which provides data and tools for the analysis of the Internet infrastructure. The CAIDA dataset is collected by a globally distributed set of monitors. The monitors collect data by sending probe messages continuously to destination IP addresses. Destinations are selected randomly from each routed IPv4/24 prefix on the Internet such that a random address in each prefix is probed approximately every 48 hours. The current prefix list includes approximately 7.4 million prefixes. For each destination selected, the path from the source monitor to the destination is collected, in particular, data collected for each path probed includes the set of IP addresses of the hops which form the path and the Round Trip Times (RTT) of both intermediate hops and the destination.

We parsed the files provided by CAIDA to obtain a weighted undirected graph G IP where a node represents an IP address contained in the dataset (both source/destination hosts and intermediate hops), edges represent links among hops and weights are given by RTTs. As the graph G IP consists of n ≈ 35000 nodes, we cannot use it for the experiments, as the amount of memory required to store the routing tables of all the nodes is O(n 2 • maxdeg) for any implemented algorithm. Hence, we performed our tests on connected subgraphs of G IP induced by the settled nodes of a breadth first search starting from a node taken at random. We generated a set of different tests, each test consists of a dynamic graph characterized by: a subgraph of G IP of 5000 nodes, a set of k concurrent edge updates, where k assumes values in {5, 10, . . . , 100}. An edge update consists of multiplying the weight of a random selected edge by a value randomly chosen in [0.5, 1.5]. For each test configuration, we performed 5 different experiments and we report average values.

In order to test the implemented algorithms on random Internet-like topologies, we generated random networks with a power-law node degree distribution by using the Barabási-Albert algorithm. This kind of networks have been proven to model many real-world networks such as the Internet, the World Wide Web, citation graphs, and some social networks [START_REF] Albert | Statistical mechanics of complex network[END_REF]. A Barabási-Albert topology is generated by iteratively adding one node at a time, starting from a given connected graph with at least two nodes. A newly added node is connected to any other existing nodes with a probability that is proportional to the degree of the existing nodes. Hence, the more connected a node is, the more likely it is to receive new connections to the new node. This mechanism is known as preferential attachment and it has been observed in many real-world networks. In detail, we randomly generated a set of different tests, where a test consists of a dynamic graph characterized by a Barabási-Albert random graphs G BA of 5000 nodes and a set of k concurrent edge updates, where k assumes values in {5, 10, . . . , 100}. Edge weights are non-negative real numbers randomly chosen in [START_REF]Omnet++: the discrete event simulation environment[END_REF]10000]. Edge updates are randomly chosen as in the CAIDA tests. For each test configuration, we performed 5 different experiments and we report average values.

Graphs G IP and G BA turn out to be very sparse (i.e. m/n ≈ 1.3), so it is worth analyzing also dense graphs. To this aim we generated Erdős-Rényi random graphs. In detail, we randomly generated a set of different tests, where a test consists of a dynamic graph characterized by: an Erdős-Rényi random graphs G ER of 1000 nodes; the density dens of the graph, computed as the ratio between m and the number of the edges of the n-complete graph; and the number k of edge update operations. We chose different values of dens ranging from 0.01 to 0.41. The number k assumes values in {30, 100, 1000}. Edge weights are non-negative real numbers randomly chosen in [START_REF]Omnet++: the discrete event simulation environment[END_REF]10000]. Edge updates are randomly chosen as in the CAIDA tests. For each test configuration, we performed 5 different experiments and we report average values.

Finally, in order to compare DUST with DEC and INC, we executed experiments on graphs G IP , G BA and G ER with sequences of only weight increase operations or only weight decrease operations, respectively. In particular, we used the same graphs and the same number of weight change operations as in the previous experiments, but the edge weights are only increased or decreased by a value randomly chosen in [1.01, 1.5] and [0.01, 0.5], respectively.

Analysis. In our experiments on fully dynamic sequences of changes, we verified that DBF is always outperformed by both DUST and DUAL. In fact, it sends a number of messages that is a factor between 32 and 295 (24 and 166, respectively) higher than the number of messages sent by DUST (DUAL, respectively). The space occupancy per node required by DBF is slightly smaller than that required by DUAL and it is always at least 100 times higher than that required by DUST. Moreover, in the tests where k ≥ 25, DBF always counts to infinity, while DUST and DUAL always converge to the correct routing tables (see Sections 2 and 3.3). For these reasons, we focus only on the comparison between DUST and DUAL, and the results of these experiments are shown in Figures 910111213141516.

In Figure 9 we report the number of messages sent by DUST and DUAL on subgraphs of G IP having 5000 nodes and an average value of 6109 edges in the cases where the number k of modifications is in {5, 10, . . . , 100}. The figure shows that DUST always sends less messages than DUAL. Figure 10 shows the results of Figure 9 from a different point of view, that is, it shows the ratio between the number of messages sent by DUAL and DUST. It is worth noting that the ratio is within 1.04 and 2.52 which means that DUAL sends a number of messages which is between 4% and 152% higher than the number of messages sent by DUST.

To conclude our analysis on G IP , we experimentally analyze the space occupancy per node. As already observed, in real-world graphs it is not common to have more than one via to a destination. Thus, the memory requirement of DUST in G IP is much smaller than that of DUAL. In particular, DUST requires in average 40000 bytes per node and 40266 bytes per node in the worst case. DUAL requires in average 186090 bytes per node and 5.2M bytes per node in the worst case. This implies that DUAL requires in average 4.65 times the space required by DUST and 129 times the space required by DUST in the worst case. The good performances of DUST in terms of memory consumption are also confirmed by the fact that, in our simulated environment, we have been able to run DUST on subgraphs of CAIDA networks with about 10000 nodes, while we have not been able to run such experiments for DUAL.

Regarding Barabási-Albert graphs, we performed similar tests as for G IP . Figure 11 and 12 report the number of messages sent by DUST and DUAL and the ratio between the number of messages sent by DUAL and DUST on such graphs. In most of the cases, DUAL is better than DUST, in fact DUST sends about twice the number of messages sent by DUAL. This is due to the get-dist messages sent by DUST whose number grows proportionally to the average node degree. In contrast, DUAL does not send such messages but it needs to store for each node the estimated distances of all its neighbors. As G BA graphs are in average denser than G IP graphs, this determines an improvement in the number of messages sent and an increase in the space occupancy per node wrt DUST. In fact in G BA graphs, DUST requires in average 40000 bytes per node and 40014 bytes per node in the worst case. DUAL requires in average 187420 bytes per node and 5.6M bytes per node in the worst case. This implies that DUAL requires in average 4.69 times the space required by DUST and 141 times the space required by DUST in the worst case.

The good performance of DUST is mainly due to the topological structure of graphs G IP and G BA . In fact, as already observed, the node degree affects the performances of DUST and DUAL in terms of both the number of messages sent and space occupancy per node. Therefore, it is worth investigating how the two algorithms perform on dense graphs. Figure 13 shows the number of messages sent by DUST and DUAL on dynamic Erdős-Rényi random graphs with 1000 nodes, 1000 edge cost changes and dens ranging from 0.01 to 0.41 which leads to a number m of edges which ranges from about 5000 to about 200000. Figure 14 shows the ratio between the number of messages sent by DUAL and DUST in the same setting as in Figure 13.

As in the case of Barabási-Albert graphs, DUAL is better than DUST in terms of number of messages sent. It is more evident here that this is due to the get-dist messages of DUST. It is also more evident the increase in space occupancy required by DUAL, as highlighted by Figures 15 and16. In detail, Figure 15 shows the ratio between the average space occupancy per node required by DUAL and DUST in G ER , while Figure 16 shows the ratio between the worst case space occupancy per node required by DUAL and DUST. The average space occupancy ratio grows linearly with the number of edges as the space occupancy of DUST remains almost constant while the space occupancy of DUAL is proportional to the average node degree. The worst case space occupancy of DUAL grows very fast as in the executed tests where dens > 0.10 there exists at least a node v such that deg(v) = n -1.

Figures 13141516refer to the case where k = 1000, as it is the case where DUST performs worse. In cases where k ∈ {30, 100} DUST performs better than the case where k = 1000, and hence they are not reported.

A summary of the performances of the three implemented algorithms in the three classes of graphs considered in the case of fully dynamic sequences is reported in Table 1, where worst case ratio for each parameter are reported.

To conclude our experimental analysis, we have compared the performances of DUST with those of DEC and INC on sequences of only weight increase operations and only weight decrease operations, respectively. The results of these experiments on Barabási-Albert instances are shown in Figures 17 and18. The results on CAIDA and Erdős-Rényi instances are similar and hence they are not reported. Figure 17 shows that DUST is slightly better than DEC in terms of number of messages sent. We recall that this is due to the application of heuristic crh 2 of DUST which is not used in DEC. The differences in space occupancy per node is negligible as the two algorithms use the same data structures. Regarding INC, it has an almost optimal message complexity and, as expected, it sends less messages than DUST as shown in Figure 18. However the number of messages sent by DUST is at most 55% more that that sent by INC. Despite the theoretical bounds, we experimentally verified that DUST and INC have similar space occupancy, again this is due to the fact that it is not common to have more than one via to a destination.

Conclusion and future work

We have studied the problem of dynamically update all-pairs shortest paths in a distributed network while edge update operations concurrently occur to the network. We have provided a new algorithm, denoted as DUST, for this problem, and experimentally compared its performance on fully dynamic sequences of updates with respect to the most popular solutions in the literature: DBF and DUAL. Furthermore, we have compared DUST with the INC and DEC algorithms of [START_REF] Cicerone | Partially dynamic algorithms for distributed shortest paths and their experimental evaluation[END_REF] on sequences of only weight decrease operations and sequences of only weight increase operations, respectively. As input to the algorithms, we used both real-world (Internet-like) and artificial instances of the problem. The results of our experiments show that the space occupancy per node required by DUST is much smaller than that required by both DBF and DUAL. In terms of messages, DUST outperforms both DBF and DUAL on the real-world topologies, while in artificial instances, it sends a number of messages that is more than that of DUAL and much smaller than that of DBF. Regarding the comparison, with INC and DEC, the space occupancy of such algorithms is always comparable to that of DUST. In terms of number of messages sent, in the incremental case, DUST is slightly worse than INC and in the decremental case, it is slightly better than DEC.

A research direction which deserves further investigation is surely that of studying new efficient algorithms or heuristic improvements of the algorithms studied in this paper for the problem of distributed shortest paths. One way could be that of modifying DUST in order to avoid routing table loops. From this point of view, a possibility is that of embedding DUST into the loopprevention framework given in [START_REF] Ray | Always acyclic distributed path computation[END_REF]. Another challenging problem is that of concentrating on real-world networks, to investigate whether structural properties of these networks can lead to the development of efficient algorithms explicitly tailored to them.

APPENDIX Example of execution

In what follows, we give an example of the execution of DBF, DUAL and DUST on a simple network (which is part of an example in [START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF]) where a weight increase operation occurs. Figure 19 shows an example of DBF. The example focuses on the graph of Figure 19(a) and on destination s. In the figure, the value close to a node indicates its distance to node s and an arrowhead from x to y in edge (x, y) indicates that node y is the successor of x towards node s. An arrowhead from x to y close to edge (x, y) denotes that node x is sending a message to y containing the current distance from s to t, the value of such distance is reported close to the arrow. At a certain point in time, edge (b, s) changes its weight from 2 to 10 (see Figure 19 Figure 20 shows an example of DUAL. The example focuses on the same graph of Figure 19(a), which is reported in Figure 20(a), and on destination s. In the figure, the value close to a node indicates its distance to node s, and an arrowhead from x to y in edge (x, y) indicates that node y is the successor of x toward node s. Messages query, reply, and update are denoted by Q, R, and U, respectively. The number in parentheses following R denotes the reported distance contained in the reply message. Nodes involved in a diffuse computation are highlighted in white.

At a certain point in time, edge (b, s) changes its weight from 2 to 10 (Figure 20(a)). When node b detects the weight increase, it determines that it has no feasible successor as none of its neighbors has a distance smaller than its current distance, that is 2. Accordingly, it starts a diffuse computation by sending a query to its neighbors (Figure 20(b)). In Figure 20(c), node c forwards the query and continues the diffuse computation, because it has no feasible successor, while node a finds a feasible successor which is node s itself as 0 < 3 and sends a reply to b. When node d receives node b's query, it simply sends a reply because it has a feasible successor. However, it becomes involved in the diffuse computation when it receives the query from node c (Figure 20(d)). When node d receives all the replies to its query (Figure 20(e)), it computes its new distance and successor (12 and c, respectively), and sends a reply to c's query (Figure 20(f)). Nodes c and b operate in a similar manner when they receives all the replies to their respective queries (Figure 20(f)-20(g)). At this point, the diffuse computation is terminated and node b sends messages update containing the new computed distance to notify it to its neighbors (Figure 20(h)). Such messages are propagated to the entire network in order to update the distances according to paths to s induced by successors nodes (Figure 20(i)). Figure 21 shows an example of DUST. The example focuses on the same graph of Figures 19(a) and 20(a), which is reported in Figure 21(a), and on destination s. As in Figures 19 and20 , the value close to a node indicates its distance to node s, and an arrowhead from x to y in edge (x, y) indicates that node y is in the set VIA[x, s], note that in this example these sets have only one element. Messages get-dist, increase, and decrease are denoted by g, i, and d, respectively. The number in parentheses following d denotes the reported distance contained in the decrease message. Moreover, messages containing replies to get-dist are represented by the reported distance close to the message arrow.

Figure 2

 2 shows the steps required by DBF to update both the distance and

Fig. 2 .

 2 Fig. 2. The sequence of recomputations of D[u, s] and VIA[u, s], u ∈ G, performed by DBF. The via to s is represented by a dotted arrow, while the number that lies close to the arrow represents the estimated distance.

Fig. 6 .

 6 Fig. 6. Scenario for Case 1: only shortest paths from v to s in G k are represented.

Fig. 7 .

 7 Fig. 7. Scenario for Case 2: only shortest paths from v to s in G 0 are represented.

Fig. 8 .

 8 Fig. 8. The sequence of recomputations of D[u, s] and VIA[u, s], u ∈ G, performed by DUST.

  in order to fully appreciate our strategy to reduce the count-to-infinity phenomenon. Consider a graph G ′ obtained from G by adding the edge (s, a) with w(s, a) = 98. In this case, when a and b receive the increase message from v, they update their routing tables as follows: D[a, s] = 98 and D[b, s] = 101. At this point node a performs crh 2 by sending a decrease message to b and to v. When b and v perform Procedure Decrease, they set D[b, s] = D[v, s] = 99 and VIA[b, s] = VIA[v, s] = {a}. Notice that, DBF still counts to infinity on G ′ , but, in this case, the counting stops after a number of updating that depends on the weight of the edge (s, a). To conclude our comparison of DUST and DBF, we give an example where they both DBF and DUST count to infinity. Let us consider the graph of Figure 1 where the weight of edge (a, v) is set to 2. At time t 0 , D[a, s] = 3 and VIA[a, s] = {v, b}. Now, the weight of edge (s, v) increases to 100. When v executes rebuild-table phase, it receives ∞ by b but it receives 3 from a and sets D[v, s] = 5 and VIA[v, s] = {a}. Then v sends increase messages to a and b. Let us assume that the message sent to a is received before that sent to b. Then, when a receives such message, it performs reduce-via and sets VIA[a, s] = {v, b} \ {v} = {b}. When b receives the increase message by v it performs rebuild-table and sets VIA[b, s] = {v}. In the resulting configuration VIA[•, s] forms a loop, the count-to-infinity phenomenon occurs and the number of messages sent depends on the new weight on the edge (s, v).

  decreases over time) and that each node u in VIA[y, s] have been added to such set as a consequence of a decrease message m = decrease(u, s, D tu [u, s]) sent by u to y. If ti0 > t u is the time when y receives m, we have Dt i 0 [y, s] ≥ w(y, u) + D tu [u, s]. Let P be the path from y to s containing u whose estimated weight is w(y, u) + D tu [u, s]. Since y received m, P must contain an edge whose weight has been changed by an operation c ∈ C. If c is a weight decrease operation, then P must contain also an edge whose weight has been increased by another operation in C. In fact, since D[y, s] decreases over time, we have that d 0 (y, s) ≥ Dt i 0 [y, s] ≥ w(y, u) + D tu [u, s],

Fig. 9 .Fig. 10 .

 910 Fig. 9. Number of messages sent by DUST and DUAL on subgraphs of G IP .

Fig. 15 .Fig. 16 .

 1516 Fig.[START_REF] Hyun | The CAIDA IPv4 routed/24 topology dataset[END_REF]. Ratio between the space required by DUAL and DUST on graphs G ER in the average case.

Fig. 17 .Fig. 18 .

 1718 Fig. 17. Number of messages sent by DUST and DEC on graphs G BA on sequences of only weight increase operations.

  (a)). When node b detects the weight increase, it updates the value of D b [b, s] to the minimal possible value, that is D b [b, s] = min u∈N (b) {w(b, u) + D b [u, s]} = w(b, c) + D b [c, s] = 4. Then, node b sends D b [b, s] to all its neighbors (Figure 19(b)). As a consequence of such messages, nodes a and c update D a [b, s] and D c [b, s], respectively, compute their optimal distances to s that are 4 and 5, respectively, and send them to their own neighbors (Figure 19(c)). Nodes s and d only update D s [b, s] and D d [b, s], respectively. In Figure 19(d), node b updates D b [c, s] to 5 as a consequence of the message sent

Fig. 19 .

 19 Fig. 19. Example of DBF.

Fig. 20 .

 20 Fig. 20. Example of DUAL.

Fig. 21 .

 21 Fig. 21. Example of DUST.

  the estimated via from v to s.

	For sake of simplicity, we write D[v, s] and VIA[v, s] instead of RT v [s].D and
	RT v [s].VIA, respectively. As the data structures change over time, in what fol-
	lows we denote as D t [v, s] and VIA t [v, s] the value of the data structures at
	time t; we simply write D[v, s] and VIA[v, s] when the time is clear by the con-
	text. Given a destination s the set VIA[v, s] contains at most deg(v) elements.
	Hence, each node v requires O (n • deg(v)) space and the space complexity of
	DUST is hence O (maxdeg • n) per node in the worst case.

  that is at time t z2 , z 2 is performing rebuild-table phase or improve-table phase wrt destination s.

Under these hypothesis, the answer to get-dist(v, s) messages of nodes z 1 and z 2 is ∞, due to the execution of crh 1 , while we can assume that nodes u 1 , u 2 , u 3 and z 3 answer with their current estimated distances to s. By using the collected information, v updates D[v, s] and VIA[v, s] at Lines 9 and 10, respectively. Since z 1 and z 2 sent ∞ as their estimated distance to s, v does not consider such nodes as possible elements of VIA[v, s]. Node z 2 will eventually send its current estimated distance to v as a decrease message by performing crh 2 . Moreover, at a certain time t, node z 1 will receive an increase message sent by v at the end of rebuild-table phase. If z 1 does not send further messages to nodes in N (z 1 ), then VIAt[z 1 , s] ≡ VIA tz 1 [z 1 , s] ≡ {v}, and hence z 1

  Furthermore, since VIA[y, s] is never empty, the condition in line 4 of procedure Increase is always false and y never performs rebuild-table phase. This implies that for each pair of times t ′ , t ′′ such that t′ < t ′′ , D t ′ [y, s] ≥ D t ′′ [y, s] (that is, D[y, s]

s), there exists y ∈ Y s and a time t ∅ (y, s) such that VIA t ∅ (y,s) [y, s] ≡ ∅.

Proof. By contradiction, let us suppose that, for each node y in Y s and for each time t, VIA t [y, s] ≡ ∅. Let y be a node in Y s . Each node x in via 0 (y, s) sends an increase message to y as a consequence of the weight increase operation on edge (x, y). When y receives this message, it performs the reduce-via phase of Procedure Increase and deletes x from VIA[y, s]. Hence, there exists a time when VIA[y, s] contains only nodes that have been added as a consequence of other increase or decrease messages received by y.

  s), a contradiction with respect to Equation 1. Hence, in what follows, we assume that t z < t ′ l (z, s) for each z ∈ VIA tv [v, s]. If there exists a node z ∈ VIA tv [v, s] that never updates D[z, s], then, by Case 1, we have that D tz [z, s] ≥ d k (z, s) and then D tv [v, s] ≥ d k (v, s), a contradiction with respect to Equation 1. Hence, in what follows, we assume that z ∈ VIA tv [v, s] updates D[z, s] at least once. When a node z ∈ VIA tv [v, s] updates D[z, s] at time t ′ l (z, s) > t z , it sends a decrease message m. When v receives m at time t m (z, v), it performs Procedure Decrease. If, at time t ′ l (z, s), z decreases the value of D[z, s], then, v performs improve-table as a consequence of m and modifies D[v, s] after the time t ′ [v, s] = w(v, z)+D tz [z, s] for each t ≥ t v . Hence, since D[z, s] as decreased, at time t m (z, v), the condition at Line 1 of Procedure Decrease is true and v performs improve-table as a consequence of m and modifies D[v, s] after the time t ′ Under this hypothesis, each node z ∈ VIA tv [v, s] also sends an increase message m ′ that is received by v at time t m ′ (z, v). In fact, the value of D[z, s] can increase only during rebuild-table and, if D[z, s] increases, the condition at Line 13 of Procedure Increase is true. Since t v ≥ t ′ l (v, s), after t v , v can only perform phases rebuild-table, reduce-via and extend-via. Let Ext(v, s) be the set of nodes added to VIA[v, s] after t v as a consequence of an rebuild-table or a extend-via phase performed by v. We can assume that each node z in Ext(v, s) fulfills the same properties of nodes in VIA tv [v, s], that is: (a) t z < t ′ l (z, s), (b) z updates D[z, s] at least once, (c) at time t ′ l (z, s), z increases the value of D[z, s] and then it sends an increase message m ′ that is received by v at time t m ′

l (v, s), a contradiction with respect to the definition of

t ′ l (v, s). In fact, since t v ≥ t ′ l (v, s), after t v , D t [v,

s] does not change and then D t l (v, s). Hence, let us assume that each node z ∈ VIA tv [v, s], at time t ′ l (z, s), increases the value of D[z, s].

  table nor extend-via phase. -if m = increase(z, s), where z ∈ N (s), then, since VIA tm [s, s] ≡ ∅, the condition in line 1 of procedure Increase is false. Thus v does not perform neither reduce-via nor rebuild-table phase. In any case, s does not change RT s [s] then, if s receives further messages, the same arguments can be used to prove the statement. Hence t F (s, s) = t 1 . Inductive step: the inductive hypothesis is: each node v such that L s (v) ≤ l-1 correctly assigns D tF (v,s) [v, s] and VIA tF (v,s) [v, s]. Let v be a node such that L s (v) = l. Each node u in via k (v, s) satisfy the inductive hypothesis. Now we show that there exists a time t D (v, s) such that, for each t ≥ t D (v, s), D t [v, s] = d k (v, s). We analyze different cases according to the behavior of nodes in via k (v, s). -If each node u in via k (v, s) does not send any message to v, then, it does not perform rebuild-table and improve-table phases and then it never changes D[u, s]. Hence, by inductive hypothesis, for each time t, D

t [u, s] = d 0 (u, s) = d k (u, s). Furthermore, since u does not change its distance to s, we have d 0 (v, s) ≤ d k (v, s). Hence, at time t 1 :

  Number of messages sent by DUST and DUAL on G BA graphs. Ratio between the number of messages sent by DUAL and DUST on G BA graphs.

	1.8e+07
	1.6e+07	DUST
	1.4e+07	DUAL
	1.2e+07
	1e+07
	8e+06
	6e+06
	4e+06
	2e+06
			0
			0	10	20	30	40	50	60	70	80	90	100
							number of modifications
	0.8 0.75 0.7 0.65 0.6 0.55 0.5 0.45 0.4 0.35 0.3 0.25	0	60 Fig. 11. number of modifications 50 40 30 20 10	70	80	90	100
	Fig. 12.

  Number of messages sent by DUST and DUAL on graphs G ER . Ratio between the number of messages sent by DUAL and DUST on graphs G ER .

	4.5e+07
	4e+07			DUST
	3.5e+07			DUAL
	3e+07
	2.5e+07
	2e+07
	1.5e+07
	1e+07
	5e+06
			0
			0	50000	100000	150000	200000
					number of edges
	0.56 0.54 0.52 0.5 0.48 0.46 0.44 0.42 0.4 0.38	0	100000 Fig. 13. number of edges 50000	150000	200000
	Fig. 14.

Table 1 .

 1 Ratio of messages sent (msg) and space occupancy per node (space) with respect to algorithm DUST, in graphs G IP , G BA , and G ER . Message sent by DBF are not reported in the cases where it counts to infinity.

			G IP	G BA	G ER
		msg	space	msg	space	msg	space
	DUST	1	1	1	1	1	1
	DBF	295	102	/	111	/	500
	DUAL	2.52	129	0.48	141	0.43	613

If the operation on edge (x i , y i ) is a delete operation, then y i (x i , respectively) cannot receive any message by x i (y i ). In this case, y i (x i ) simulates the reception of the increase message by x i (y i ) by sending such message to itself.

Acknowledgments

Support for the IPv4 Routed/24 Topology Dataset is provided by National Science Foundation, US Department of Homeland Security, WIDE Project, Cisco Systems, and CAIDA.