A Kosowski

B Li

N Nisse

K Suchan

k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth

Keywords: Treewidth, chordality, compact routing, cops and robber games

. Moreover, any graph admitting such a tree-decomposition has small hyperbolicity. As an application, for any n-node graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(log n) bits and achieving an additive stretch of O(k log ∆). As far as we know, this is the first routing scheme with O(k log ∆ + log n)-routing tables and small additive stretch for k-chordal graphs.

Introduction

Because of the huge size of real-world networks, an important current research effort concerns exploiting their structural properties for algorithmic purposes. Indeed, in large-scale networks, even algorithms with polynomial-time in the size of the instance may become unpractical. So, it is important to design algorithms depending only quadratically or linearly on the size of the network when its topology is expected to satisfy some properties. Among these properties, the chordality of a graph is the length of its longest induced (i.e., chordless) cycle. The hyperbolicity of a graph reflects how the metric (distances) of the graph is close to the metric of a tree. A graph has hyperbolicity ≤ δ if, for any u, v, w ∈ V (G) and for any shortest paths P uv , P vw , P uw between these three vertices, any vertex in P uv is at distance at most δ from P vw ∪ P uw [START_REF] Gromov | Hyperbolic groups[END_REF]. Intuitively, in a graph with small hyperbolicity, any two shortest paths between the same pair of vertices are close to each other. Several recent works take advantage of such structural properties of large-scale networks for algorithm design (e.g., routing [START_REF] Krioukov | Greedy forwarding in scale-free networks embedded in hyperbolic metric spaces[END_REF]). Indeed, Internet-type networks have a so-called high clustering coefficient (see e.g. [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]), leading to the existence of very few long chordless cycles, whereas their low (logarithmic) diameter implies a small hyperbolicity [START_REF] De Montgolfier | Treewidth and hyperbolicity of the internet[END_REF].

Another way to study tree-likeness of graphs is by tree-decompositions. Introduced by Robertson and Seymour, such decompositions play an important role in design of efficient algorithms. Roughly speaking, a tree-decomposition maps each vertex of a graph to a subtree of the decomposition tree in a way that the subtrees assigned to adjacent vertices intersect [START_REF] Bodlaender | A partial k-arboretum of graphs with bounded treewidth[END_REF]. The nodes of the decomposition tree are called bags, and the size of a bag is the number of vertices assigned to it (assigned subtrees intersect the bag). The width of a treedecomposition is the maximum size over its bags, and the treewidth of a graph is the smallest width over its tree-decompositions. By using dynamic programming based on a tree-decomposition, many NP-hard problems have been shown to be linear time solvable for graph with bounded treewidth [START_REF] Courcelle | Monadic second-order evaluations on treedecomposable graphs[END_REF]. In particular, there are linear-time algorithms to compute an optimal tree-decomposition of a graph with bounded treewidth [START_REF] Bodlaender | Efficient and constructive algorithms for the pathwidth and treewidth of graphs[END_REF]. However, from the practical point of view, this approach has several drawbacks. First, all above-mentioned algorithms are linear in the size of the graph but (at least) exponential in the treewidth. Moreover, due to the high clustering coefficient of large-scale networks, their treewidth is expected to be large [START_REF] De Montgolfier | Treewidth and hyperbolicity of the internet[END_REF]. Hence, to face these problems, it is important to focus on the structure of the bags of the tree-decomposition, instead of trying to minimize their size. For instance, several works study the diameter of the bags [START_REF] Dourisboure | Tree-decompositions with bags of small diameter[END_REF]. In this work, we consider tree-decompositions in which each bag admits a particular small dominating set. Such decompositions turn out to be applicable to a large family of graphs (including k-chordal graphs).

Our results

Our results on tree decomposition are inspired by a study of the so called cops and robber games. The aim of such a game is to capture a robber moving in a graph, using as few cops as possible. This problem has been intensively studied in the literature, allowing for a better understanding of the structure of graphs [START_REF] Bonato | The game of Cops and Robber on Graphs[END_REF].

Outline of the paper. We start by presenting our results for the cops and robber problem in Section 2. Next, using these results, in Section 3 we provide a new type of efficiently computable tree-decomposition which we call good tree decomposition. Our tree decomposition turns out to be applicable to many real-world graph classes (including k-chordal graphs), and has several algorithmic applications. Finally, we focus on the applications of this decomposition to the compact routing problem, a research area in which tree decompositions have already proved useful [START_REF] Dourisboure | Compact routing schemes for generalised chordal graphs[END_REF]. The objective of compact routing is to provide a scheme for finding a path from a sender node to a known destination, taking routing decisions for the packet at every step using only very limited information stored at each node. In Section 4, we show how to use our tree decomposition to minimize the additive stretch of the routing scheme (i.e., the difference between the length of a route computed by the scheme and that of a shortest path connecting the same pair of nodes) in graphs admitting with k-good tree-decomposition for any given integer k ≥ 3 (including k-chordal graphs), assuming logarithmic size of packet headers and routing tables stored at each node.

The necessary terminology concerning cops and robber games, tree decompositions, and compact routing, is introduced in the corresponding sections.

Main contributions. Our main contribution is the design of a O(m 2 ) algorithm that, given a m-edge graph G and an integer k ≥ 3, either returns an induced cycle of length at least k + 1 in G or computes a tree-decomposition of G with each bag having a dominating path of order ≤ k -1. That is, each bag of our tree-decomposition contains a chordless path with at most k -1 vertices, such that any vertex in the bag is either in the path or adjacent to some vertex of the path. If G, with maximum degree ∆, admits such a decomposition, then G has treewidth at most (k -1)(∆ -1) + 2, tree-length at most k and hyperbolicity at most 3 2 k . In particular, this shows that the treewidth of any k-chordal graph is upper-bounded by O(k • ∆), improving the exponential bound of [START_REF] Bodlaender | Treewidth for graphs with small chordality[END_REF]. The proposed algorithm is mainly derived from our proof of the fact that k -1 cops are sufficient to capture a robber in k-chordal graphs.

Our tree-decomposition may be used efficiently for solving problems using dynamic programming in graphs of small chordality and small maximum degree. In this paper, we focus on different application. We present a compact routing scheme that uses our tree-decomposition and that achieves an additive stretch ≤ 2k( log ∆ + 5

2 ) -5 with routing tables, addresses and message headers of O(max{k•log ∆, log n}) bits. An earlier approach of Dourisboure achieved stretch k + 1, but with routing tables of size O(log 2 n).

Related Work

Chordality and hyperbolicity. Chordality and hyperbolicity are both parameters measuring the tree-likeness of a graph. Some papers consider relations between them [START_REF] Wu | Hyperbolicity and chordality of a graph[END_REF]. In particular, the hyperbolicity of a k-chordal graph is at most k, but the difference may be arbitrary large (take a 3 × n-grid). The seminal definition of Gromov hyperbolicity is the following. A graph G is d-hyperbolic provided that for any vertices x, y, u, v ∈ V (G), the two larger of the three sums d(u, v)+d(x, y), d(u, x)+d(v, y) and d(u, y)+d(v, x) differ by at most 2d [START_REF] Gromov | Hyperbolic groups[END_REF]. This definition is equivalent to the one we use in this paper, using so called thin triangles, up to a constant ratio. No algorithm better than the O(n 4 )-brute force algorithm (testing all 4-tuples in G) is known to compute Gromov hyperbolicity of n-node graphs. The problem of computing the chordality of a graph G is NP-complete since it may be related to computing a longest cycle in the graph obtained from G after subdividing all edges once. Finding the longest induced path is W [2]-complete [START_REF] Chen | On parameterized path and chordless path problems[END_REF] and the problem is Fixed Parameter Tractable in planar graphs [START_REF] Kobayashi | Algorithms for finding an induced cycle in planar graphs and bounded genus graphs[END_REF].

Treewidth. It is NP-complete to decide whether the treewidth of a graph G is at most k [START_REF] Arnborg | Complexity of finding embeddings in a k-tree[END_REF]. The treewidth problem is polynomially solvable in chordal graphs, cographs, circular arc graphs, chordal bipartite graphs, etc. [START_REF] Bodlaender | A partial k-arboretum of graphs with bounded treewidth[END_REF]. Bodlaender and Thilikos proved that the treewidth of a k-chordal graph with maximum degree ∆ is at most ∆(∆-1) k-3 which implies that treewidth is polynomially computable in the class of graphs with chordality and maximum degree bounded by constants [START_REF] Bodlaender | Treewidth for graphs with small chordality[END_REF]. They also proved that the treewidth problem is NP-complete for graphs with small maximum degree [START_REF] Bodlaender | Treewidth for graphs with small chordality[END_REF].

Compact routing. In [AGM + 08], a universal name-independent routing scheme with stretch linear in k and n 1/k polylog(n) space is provided. There are weighted trees for which every name-independent routing scheme with space less than n 1/k requires stretch at least 2k + 1 and average stretch at least k/4 [START_REF] Abraham | On space-stretch trade-offs: Lower bounds[END_REF]. Subsequently, the interest of the scientific community was turned toward specific properties of graphs. Several routing schemes have been proposed for particular graph classes: e.g., trees [START_REF] Fraigniaud | Routing in trees[END_REF], bounded doubling dimension [START_REF] Abraham | Routing in networks with low doubling dimension[END_REF], excluding a fixed graph as a minor [START_REF] Abraham | Object location using path separators[END_REF], etc.The best compact routing scheme in k-chordal graphs (independent from the maximum degree) is due to Dourisboure and achieves a stretch of k +1 using routing tables of size O(log 2 n) bits [START_REF] Dourisboure | Compact routing schemes for generalised chordal graphs[END_REF]. A routing scheme achieving stretch k -1 with a distributed algorithm for computing routing tables of size O(∆ log n) bits has been proposed in [START_REF] Nisse | Distributed computing of efficient routing schemes in generalized chordal graphs[END_REF].

A detour through Cops and Robber games

Let us first fix some notations. G denotes a simple connected undirected graph with vertex set V and edge set E. n = |V | is the order of G and m = |E| is the size of G. V (H) and E(H) denotes the vertex and edge set of H, respectively. The set of vertices adjacent to

v ∈ V is denoted N (v) and called open neighborhood of v. N [v] = N (v) ∪ {v} is the closed neighborhood of v. We extend this notation to write N [U ] = ∪{N [u] | u ∈ U } and N (U ) = N [U ] \ U . d G (v) = |N G (v)
| is the degree of v, ∆ denotes the maximum degree among the vertices of G. The graph obtained from G by removing an edge {x, y} is denoted G \ {x, y}; the result of removing a vertex v and all adjacent edges is denoted G \ {v}. Like above, we extend this to denote removing sets of vertices or edges. For U ⊂ V , G[U ] is the subgraph of G induced by U . It can be obtained as the result of removing from G the vertices in V \ U , denoted by G \ (V \ U ). Given two paths P = (p 1 , . . . , p k ) and Q = (q 1 , . . . , q r ), we denote by (P, Q) the path present in the graph induced by V (P ) ∪ V (Q) -to make descriptions more concise, we omit the detail of reversing P or Q if necessary.

Let us formally define a cops' strategy to capture a robber. Given a graph G, a player starts by placing k ≥ 1 cops on some vertices in V , then a visible robber is placed on one vertex v in V . Alternately, the robber can move to a vertex x in N (v), and the cop-player may move each cop along an edge. The robber is captured if, at some step, a cop occupies the same vertex. The copnumber of a graph G, denoted by cn(G), is the fewest number of cops required to capture a robber in G (see the recent book [START_REF] Bonato | The game of Cops and Robber on Graphs[END_REF]). Bounds on the cop-number have been provided for various graph classes and provided many nice structural results [START_REF] Bonato | The game of Cops and Robber on Graphs[END_REF]. We consider the class of k-chordal graphs.

Theorem 1. Let k ≥ 3. For any k-chordal connected graph G, cn(G) ≤ k -1, and there exists a strategy where all k -1 cops always occupy a chordless path.

Proof. Let v ∈ V be any vertex and place all cops at it. Then, the robber chooses a vertex. Now, at some step, assume that the cops are occupying {v 1 , • • • , v i } which induce a chordless path, i ≤ k -1, and it is the turn of the cops (initially i = 1). Let N = ∪ j≤i N [v j ], if the robber occupies a vertex in N , it is captured during the next move. Else, let R = ∅ be the connected component of G \ N occupied by the robber. Finally, let S be the set of vertices in N that have some neighbor in R. Clearly, while R is not empty, then so does S. Now, there are two cases to be considered.

If N (v 1 ) ∩ S ⊆ ∪ 1<j≤i N [v j ]
. This case may happen only if i > 1. Then, "remove" the cop(s) occupying v 1 . That is, the cops occupying

v 1 go to v 2 . Symmetrically, if N (v i ) ∩ S ⊆ ∪ 1≤j<i N [v j ],
then the cops occupying v i go to v i-1 . Then, the cops occupy a shorter chordless path while the robber is still restricted to R.

Hence, there is u

∈ (N (v 1 ) ∩ S) \ (∪ 1<j≤i N [v j ]) and v ∈ (N (v i ) ∩ S) \ (∪ 1≤j<i N [v j ]
). First, we show that this case may happen only if i < k -1. Indeed, otherwise, let P be a shortest path between such u and v with all internal vertices in R (possibly, P is reduced to an edge). Such a path exists by definition of S. Then, (v

1 , • • • , v i , v, P, u) is a chordless cycle of length at least i+2. Since G is k-chordal, this implies that i + 2 ≤ k. Then, one cop goes to v = v i+1 while all the vertices in {v 1 , • • • , v i } remain occupied. Since v ∈ S,
it has some neighbor in R, and then, the robber is restricted to occupy R the connected component of G \ (N ∪ N [v]) which is strictly contained in R.

Therefore, proceeding as described above strictly reduces the area of the robber (i.e., R) after < k steps and then the robber is eventually captured.

Note that previous Theorem somehow extends the model in [START_REF] Clarke | Tandem-win graphs[END_REF] where the authors consider the game when two cops always remaining at distance at most 2 from each other must capture a robber. It is possible to improve the previous result in case k = 4. Indeed, for any 4-chordal connected graph G, then cn(G) ≤ 2. Due to lack of space, the proof is omitted and can be found in [START_REF] Kosowski | k-chordal graphs: from cops and robber to compact routing via treewidth[END_REF].

Theorem 1 relies on chordless paths P in G such that N [P ] is a separator of G, i.e., there exist vertices a and b of G such that all paths between a and b intersect N [P ]. In next section, we show how to adapt this to compute particular tree-decompositions.

Structured Tree-decomposition

In this section, we present our main contribution, that is, an algorithm that, given a n-node graph G and an integer k ≥ 3, either returns an induced cycle of length at least k + 1 in G or computes a tree-decomposition of G with interesting structural properties. First, we need some definitions.

A tree-decomposition of a graph G = (V, E) is a pair ({X i |i ∈ I}, T = (I, M )), where T is a tree and {X i |i ∈ I} is a family of subsets, called bags, of vertices of G such that (1) V = ∪ i∈I X i ; (2) ∀{uv} ∈ E there is i ∈ I such that u, v ∈ X i ; and (3) ∀v ∈ V , {i ∈ I|v ∈ X i } induces a (connected) subtree of T . The width of a tree-decomposition is the size of its largest bag minus 1 and its -width is the maximum diameter of the subgraphs induced by the bags. The treewidth denoted by tw(G), resp., tree-length denoted by tl(G), of a graph G is the minimum width, resp., -width, over all possible tree-decompositions of G [START_REF] Dourisboure | Tree-decompositions with bags of small diameter[END_REF].

Let k ≥ 2. A k-caterpillar is a graph that has a dominating set, called backbone, which induces a chordless path of order at most k -1. That is, any vertex of a k-caterpillar either belongs to the backbone or is adjacent to a vertex of the backbone. A tree-decomposition is said to be k-good if each of its bags induces a k-caterpillar.

Theorem 2. There is a O(m 2 )-algorithm that takes a graph G of size m and an integer k ≥ 3 as inputs and: either returns an induced cycle of length at least k + 1; or returns a k-good tree-decomposition of G;

Proof. The proof is by induction on |V (G)| = n. We prove that either we find an induced cycle larger than k, or for any chordless path P = (v 1 , . . . , v i ) with i ≤ k -1, there is a k-good tree-decomposition for G with one bag containing N G [P ]. Obviously, it is true if |V (G)| = 1. Now we assume that it is true for any graph G with n nodes, 1 ≤ n < n, and we show it is true for n-node graphs.

Let G be a connected n-node graph, n > 1. Let P = (v 1 , . . . , v i ) be any chordless path with i ≤ k -1 and let N = N G [P ], N j = N G [v j ] for j = 1, . . . , i and G = G \ N . There are three cases to be considered: Case 1. G = ∅. In this case, we have G = N . The desired tree-decomposition consists of one node, corresponding to the bag N . Case 2. G is disconnected. Let C 1 , . . . , C r , r ≥ 2, be the connected components of G For any j ≤ r, let G j be the graph induced by C j ∪ N . Note that any induced cycle in G j , j ≤ r, is an induced cycle in G. By the induction hypothesis, either there is an induced cycle C larger than k in G j , then C is also an induced cycle larger than k in G, or our algorithm computes a k-good tree-decomposition T D j of G j with one bag X j containing N . To obtain the k-good tree-decomposition of G, we combine the T D j 's, j ≤ r, by adding a bag X = N adjacent to all the bags X j for j = 1, . . . , r. It is easy to see that this tree-decomposition satisfies our requirements. Case 3. G is connected. We consider the order of the path P = (v 1 , . . . , v i ). In the following proof, first we prove that if the order of path P , i = k -1, then we can find either an induced cycle larger than k or the required treedecomposition for G. Subsequently, we prove it is also true for path with length i < k -1 by reversed induction on i. More precisely, if i < k -1, either we find directly the desired cycle or tree-decomposition, or we show that there exists a vertex v i+1 such that V (P ) ∪ {v i+1 } induces a chordless path P' of order i + 1. By reverse induction on i we can find either an induced cycle larger than k or a k-good tree-decomposition of G with one bag containing

N G [V (P )] ⊇ N G [V (P )].
(a) If i = k -1, then we consider the following two cases.

-Assume first that there is u

∈ N G (V (P )) ∪ {v 1 , v i } (in particu- lar, u / ∈ V (P ) \ {v 1 , v i }) such that N G (u) ⊆ N G [V (P ) \ {u}]. Let G = G \ {u}.
Then G is a graph with n = n -1 vertices. By the induction hypothesis on n < n, the algorithm either finds an induced cycle larger than k in G, then it is also the one in G; Otherwise our algorithm computes a k-good tree-decomposition T D of G with one bag X containing N G[V (P ) \ {u}]. To obtain the required tree-decomposition of G, we just add vertex u into the bag X. The tree-decomposition is still k-good.

-Otherwise, there exist two distinct vertices v 0 ∈ N G (v 1 ) and v i+1 ∈ N G (v i ) and there are vertices

u 1 , u 2 ∈ V (G ) (possibly u 1 = u 2 ) such that {v 0 , u 1 } ∈ E(G) and {v i+1 , u 2 } ∈ E(G). If {v 0 , v i+1 } ∈ E(G), (P, v 0 , v i+1
) is an induced cycle with k + 1 vertices. Otherwise, let Q be a shortest path between u 1 and u 2 in G (Q exists since G is connected). So (P, v i+1 , u 2 , Q, u 1 , v 0 ) is an induced cycle with at least k + 1 vertices in G. (b) If i < k -1, we proceed by reverse induction on i. Namely, assume that, for any chordless path Q with i + 1 vertices, our algorithm either finds an induced cycle larger than k in G or computes a k-good tree-decomposition of G with one bag containing N [Q]. Note that the initialization of the induction holds for i = k -1 as described in case (a). We show it still holds for a chordless path with i vertices. We consider the following two cases.

-Either there is u

∈ N G (V (P )) ∪ {v 1 , v i } (in particular, u / ∈ V (P ) \ {v 1 , v i }) such that N G (u) ⊆ N G [V (P ) \ {u}].
That is, we are in the same case as the first item of (a). We proceed as above and the result holds by induction on n.

-Or there is w ∈ N G (v 1 ) ∪ N G (v i ) \ V (P ) such that (P, w) is chordless (i.e., w is a neighbor of v 1 or v i but not both). Therefore, we apply the induction hypothesis (on i) on P = (P, w). By the assumption on i, either our algorithm returns an induced cycle larger than k or it computes a k-good tree-decomposition of G with one bag containing

N G [V (P )] ⊇ N G [V (P )].
Let us analyze the algorithm and its complexity. Let G be a m-edge n-node graph with maximum degree ∆. The algorithm proceeds in steps of O(m) time, each time considering one vertex. We prove that at each step (but the first one), at least one edge will be considered and that all edges are considered at most once. This implies a time-complexity of O(m 2 ) for the algorithm. Due to lack of space, the proof of the time-complexity is omitted and can be found in [START_REF] Kosowski | k-chordal graphs: from cops and robber to compact routing via treewidth[END_REF].

Due to lack of space, the proofs of the following consequences of Theorem 2 are omitted and can be found in [START_REF] Kosowski | k-chordal graphs: from cops and robber to compact routing via treewidth[END_REF].

Theorem 3. Let G be a graph that admits a k-good tree-decomposition. Then tw(G) ≤ (k -1)(∆ -1) + 2 where ∆ is its maximum degree, tl(G) ≤ k, and hyperbolicity at most 3 2 k . Corollary 1. Any k-chordal graph G with maximum degree ∆ has treewidth at most (k -1)(∆ -1) + 2, tree-length at most k and hyperbolicity at most 3 2 k . Corollary 2. There is an algorithm that, given a m-edge graph G and k ≥ 3, states that either G has chordality at least k + 1 or G has hyperbolicity at most

3 2 k , in time O(m 2 ).

Application of k-good tree-decompositions for routing

In this section, we propose a compact routing scheme for any n-node graph G that admits a k-good tree-decomposition (including k-chordal graphs). here here

Model and performance of the routing scheme

We propose a labelled routing scheme which means that we are allowed to give one identifier, name(v), of O(log n) bits to any vertex v of G. Moreover, following [START_REF] Fraigniaud | Routing in trees[END_REF], we consider the designer-port model, which allows us to choose the permutation of ports (assign a label of log d v bits to any edge incident to v in V (G)). Finally, to any node v ∈ V (G), we assign a routing table, denoted by T able(v), where local information of O(k • log ∆ + log n) bits is stored. Any message has a header that contains the address name(t) of the destination t, three modifiable integers pos ∈ {-1, 0, Following our routing scheme, a node v that receives a message uses its header, name(v), T able(v) and the port-numbers of the edges incident to v to compute its new header and to choose the edge e = {v, u} over which it relays the message. Then, the node u knows that the message arrived from v. The length of the path followed by a message from a source s ∈ V (G) to a destination t ∈ V (G), using the routing scheme, is denoted by |P (s, t)|, and the stretch of the scheme is max s,t∈V (G) |P (s, t)| -d(s, t) where d(s, t) is the distance between s and t in G.

• • • , k -1}, cnt d , cnt d ∈ {-1, 0, • • • , ∆ + 1},
To design our routing scheme, we combine the compact routing scheme in trees of [START_REF] Fraigniaud | Routing in trees[END_REF] together with the k-good tree-decomposition. Roughly, the scheme consists in following the paths in a BFS-tree F of G, using the scheme in [START_REF] Fraigniaud | Routing in trees[END_REF], and uses one bag of the tree-decomposition as a short-cut between two branches of F . Intuitively, if the source s and the destination t are "far apart", then there is a bag X of the tree-decomposition that separates s and t in G. The message follows the path in F to the root of F until it reaches X, then an exhaustive search is done in X until the message finds an ancestor y of t, and finally it follows the path from y to t in F using the scheme of [START_REF] Fraigniaud | Routing in trees[END_REF]. The remaining part of this Section is devoted to the proof of the next Theorem that summarizes the performances of our routing scheme.

Theorem 4. For any n-node m-edge graph G with maximum degree ∆ and with a k-good tree-decomposition, there is a labelled routing scheme R with the following properties. R uses addresses of size O(log n) bits, port-numbers of size O(log ∆) bits and routing tables of size O(k • log ∆ + log n) bits. The routing tables, addresses and port-numbers can be computed in time O(m 2 ). Except the address of the destination (not modifiable), the header of a message contains O(k • log ∆) modifiable bits. The header and next hop is computed in time O(1) at each step of the routing. Finally, the additive stretch is ≤ 2k( log ∆ + 5 2 ) -5.

Data structures

Routing in trees [START_REF] Fraigniaud | Routing in trees[END_REF]. Since, we use the shortest path routing scheme proposed in [START_REF] Fraigniaud | Routing in trees[END_REF] for trees, we start by recalling some of the data structures they use. Let F be a tree rooted in r ∈ V (F ). For any v ∈ V (F ), let F v be the subtree of F rooted in v and let w F (v) = |V (F v )| be the weight of v. Consider a Depth-First-Search (DF S) traversal of F , starting from r, and guided by the weight of the vertices, i.e., at each vertex, the DFS visits first the largest subtree, then the second largest subtree, and so on. For any v ∈ V (F ), let

Id F (v) ∈ {1, • • • , n} be the preordering rank of v in the DF S. It is important to note that, for any u, v ∈ V (F ), v ∈ V (F u ) if and only if Id F (u) ≤ Id F (v) ≤ Id F (u) + w F (u) -1.
For any v ∈ V (F ) and any e incident to v, the edge e receives a port-number p F (e, v) at v as follows. p F (e, v) = 0 if v = r and e leads to the parent of v in F , i.e., e is the first edge on the path from v to r. Otherwise, let (u

1 , • • • , u d ) be the children of v (d = d F v if v = r and d = d F v -1 otherwise) ordered by their weight, i.e., such that w F (u 1 ) ≥ • • • ≥ w F (u d ).
Then, let p F ({u i , v}, v) = i, for any i ≤ d. Finally, each vertex v ∈ V (F ) is assigned a routing table RT F (v) and an address F (v) of size O(log n) bits allowing a shortest path routing in trees (see details in [START_REF] Fraigniaud | Routing in trees[END_REF]).

Our data structures. Let G be a graph with the k-good tree-decomposition (T = (I, M ), {X i |i ∈ I}). Let r ∈ V (G). Let F be a Breadth-First-Search(BF S) tree of G rooted at r. Let T be rooted in b ∈ I such that r ∈ X b .

We use (some of) the data structures of [START_REF] Fraigniaud | Routing in trees[END_REF] for both trees F and T . More precisely, for any v ∈ V (G), let Id F (v), w F (v), F (v) and RT F (v) be defined as above for the BF S-tree F . Moreover, we add d F (v) to store the degree of v in the tree F . p e,v = p F (e, v) for edges that belong to F are defined as above, the ports > d F (v) will be assigned to edges that do not belong to F . With d F (v) at hand, the ports that correspond to edges in F can be easily distinguished from ports assigned to edges in F .

For any i ∈ I, let Id T (i) and w T (i) be defined as above for the tree T . For any v ∈ V (G), let B v ∈ I be the bag of T containing v (i.e., v ∈ X Bv ) that is closest to the root b of T . To simplify the notations, we set Id T (v) = Id T (B v ) and w T (v) = w T (B v ). These structures will be used to decide "where" we are in the tree-decomposition when the message reaches v ∈ V (G).

Let

F = G \ E(F ). For any v ∈ V (G), let (u 1 , • • • , u d ) = N F (v) be the neighborhood of v in F ordered such that Id F (u 1 ) < • • • < Id F (u d ). We assign p ei,v = d F (v) + i
, where e i = {v, u i }, for each u i in this order. This ordering will allow to decide whether one of the vertices in N F (v) is an ancestor of a given node t in time O(log ∆) by binary search.

Finally, for any i ∈ I, let

P i = (v 1 , • • • , v
) be the backbone of B i with ≤ k-1 (recall we consider a k-good tree decomposition). Let (e 1 , • • • , e -1 ) be the set of edges of P i in order. We set Backbone i = (p e1,v1 , p e1,v2 , p e2,v2 , • • • , p e -1 ,v ). For any v ∈ V (G) such that Id T (v) = i ∈ I, if v = v j ∈ P i , then back(v) = (∅, j) and if v / ∈ P i , let back(v) = (p e,v , j) where e = {v, v j } and v j (j ≤ ) is the neighbor of v in P i with j minimum. This information will be used to cross a bag (using its backbone) of the tree-decomposition. Now, for every v ∈ V (G), we define the address name(v) = F (v), Id T (v) . Note that, in particular, F (v) contains Id F (v). We also define the routing table of

v as T able(v) = RT F (v), w T (v), Backbone(v), back(v) .
Next table summarizes all these data structures.

notation description name(v) F (v) the address of v in tree F [FG01] Id T (v) the identifier of the highest bag B v containing v in T RT F (v) the routing table used of v for routing in F [FG01] d F (v) the degree of v in F T able(v) w T (v)
the weight of the subtree of T rooted in B v Backbone(v) information to navigate in the backbone of B v back(v) information to reach the backbone of B v from v

Clearly, name(v) has size O(log n) bits and T able(v) has size O(k • log ∆ + log n) bits. Moreover, any edge e incident to v receives a port-number p e,v of size O(log ∆) bits.

Routing algorithm in k-good tree-decomposable graphs

Let us consider a message that must be sent to some destination t ∈ V (G). Initially, the header of the message contains name(t), the three counters pos, cnt d , cnt d = -1, the bit start = 0 and the memory path = ∅. Let v ∈ V (G) be the current node where the message stands. First, using Id F (t) in name(t), Id F (v) in name(v) and w F (v) in RT F (v) ∈ T able(v), it is possible to decide in constant time if v is an ancestor of t in F . Similarly, using Id T (t) in name(t), Id T (v) in name(v) and w T (v) in T able(v), it is possible to decide if the highest bag B v containing v is an ancestor of B t in T . There are several cases to be considered.

-If v is an ancestor of t in F , then using the protocol of [START_REF] Fraigniaud | Routing in trees[END_REF] the message is passed to the child w of v that is an ancestor of t in F towards t. Recursively, the message arrives at t following a shortest path in G, since F is a BF S-tree. -Else, if path = ∅, then

• if neither B v is an ancestor of B t in T nor B t = B v , then the message follows the edge leading to the parent of v in F , i.e., the edge with portnumber p e,v = 0. Note that the message will eventually reach w that either is an ancestor of t in F or B w is an ancestor of B t in T , since the message follows a shortest path to the root r of F and B r is the ancestor of any bag in T .

• Else, an ancestor of t belongs to B v since either B v = B t , or B v is an ancestor of B t . Therefore, since T is a tree-decomposition, B v has to contain a vertex on the shortest path from t to r in F . Now the goal of it is to explore the bag B v using its backbone P

= (v 1 , • • • , v ) ( < k),
until the message finds an ancestor of t in F . The aim of this case is to put the message on the backbone, and then explore the backbone using Backbone(v) copied in path in the header of the message. Using back(v) = (p, j) ∈ T able(v), pos is set to j. If p = ∅ then the message already is on the backbone. Otherwise, the message is sent over the port p. The idea is to explore the neighborhoods of vertices on the backbone, starting from v 1 . Note that at in what follows path = ∅ and pos = -1. -Else, if start = 0, then the message is at v = v j ∈ P and pos indicates the value of j. Moreover, in the field path of the header, there are the portnumbers allowing to follow P . If pos > 1 then pos = j -1 is set and the message follows the corresponding port-number to reach v j-1 . Otherwise, start is set to 1, cnt d = d F (v 1 ) and cnt d = d G (v 1 ) + 1. -Else, if start = 1, then the exploration of a bag containing an ancestor of t has begun. The key point is that any ancestor w of t in F is such that Id F (w) ≤ Id F (t) ≤ Id F (w)+w F (w)-1. Using this property, for each vertex v j of the backbone P = (v 1 , • • • , v ), the message visits v j and its parent in F , and explores N F (v j ) by binary search. Notice that the other neighbors of v j are its descendants in F , so if t has an ancestor among them, then v j also is an ancestor of t.

• If cnt d = cnt d -1, the neighborhood of the current node v = v j , where j = pos, has already been explored and no ancestor of t has been found. In that case, using path, the message goes to v j+1 the next vertex in the backbone. pos = j + 1 is set. . The message takes port-number pn from v towards vertex w. If w is an ancestor of t, we go to the first case of the algorithm. Otherwise, the message goes back to v = v j . This is possible since the node knows the port over which the message arrives. Moreover, if Id F (t) > Id F (w) + w F (w) -1, then cnt d is set to pn and cnt d is set to pn otherwise. The fact that the message eventually reaches its destination follows from the above description. Moreover, the computation of the next hop and the modification of the header clearly takes time O(1). Due to lack of space, the proof of the stretch, described in next lemma, is omitted and can be found in [START_REF] Kosowski | k-chordal graphs: from cops and robber to compact routing via treewidth[END_REF].

Lemma 1. Our routing scheme has stretch ≤ 2k( log ∆ + 5

2 ) -5.

Conclusion and Further Work

It would be interesting to reduce the O(k • log ∆) stretch due to the dichotomic search phase of our routing scheme. Another interesting topic concerns the computation of tree-decompositions not trying to minimize the size of the bag but imposing some specific algorithmically useful structure.

  one bit start and some memory, called path, of size O(k • log ∆) bits. start and path change only once.

  • Otherwise, let pn = cnt d +cnt d 2

Partially supported by programs Fondap and Basal-CMM, Anillo ACT88 and Fondecyt 11090390 (K.S.), FP7 STREP EULER (N.N.).


Laurent Bobelin

Arnaud Legrand

David A González Márquez

Pierre Navarro

Martin Quinson

Frédéric Suter

Christophe Thiéry

Scalable Multi-Purpose Network Representation for Large Scale Distributed System Simulation

Conducting experiments in large-scale distributed systems is usually time-consuming and labor-intensive. Uncontrolled external load variation prevents to reproduce experiments and such systems are often not available to the purpose of research experiments, e.g., production or yet to deploy systems. Hence, many researchers in the area of distributed computing rely on simulation to perform their studies. However, the simulation of large-scale computing systems raises several scalability issues, in terms of speed and memory. Indeed, such systems now comprise millions of hosts interconnected through a complex network and run billions of processes. Most simulators thus trade accuracy for speed and rely on very simple and easy to implement models. However, the assumptions underlying these models are often questionable, especially when it comes to network modeling.

In this paper, we show that, despite a widespread belief in the community, achieving high scalability does not necessarily require to resort to overly simple models and ignore important phenomena. We show that relying on a modular and hierarchical platform representation, while taking advantage of regularity when possible, allows us to model systems such as data and computing centers, peer-to-peer networks, grids, or clouds in a scalable way. This approach has been integrated into the opensource SIMGRID simulation toolkit. We show that our solution allows us to model such systems much more accurately than other state-of-the-art simulators without trading for simulation speed. SIMGRID is even sometimes orders of magnitude faster.

I. INTRODUCTION

The current evolution of computing and data management platforms to ever growing and more distributed infrastructures, such as Data Centers, Computing Grids, Clouds, Desktop Grids, or Peer-to-Peer (P2P) systems, raises new challenges in Computer Science. The unprecedented scale of these systems makes it difficult and costly to test new protocols or algorithms on production infrastructures. Indeed, such systems are inherently unstable, which hinders experiments reproducibility. Furthermore, real systems (e.g., a P2P network or a production computing center) are generally not available to the purpose of research experiments. Last, researchers may be interested in studying systems that do not exist yet for example when performing preliminary study or investigating the efficiency of solutions under workloads different from the ones available at hand. Hence, simulation has been extensively used to study such Large-Scale Distributed Computing (LSDC) systems.

Yet, simulating such LSDC systems raises scalability issues, both in terms of speed and memory. Indeed, such systems now comprise millions of hosts interconnected through a complex network and run billions of processes. The faithful representation of the interconnection network is generally difficult. A few simulators rely on a detailed model of the network (e.g., packet-level simulators that are heavily used in the network community) but their use in the context of distributed computing raises two difficult issues. First, such complex models are much harder to instantiate than simple ones (detailed topology, network characteristics of the whole platform, injection of realistic external background load at the packet-level, . . . ). Second, packet-level simulation is so heavy that it becomes completely unusable beyond a few thousands hosts. Hence, most simulators from these domains address scalability issues by relying on simplistic models that can be implemented efficiently although such simplifications are sometimes very debatable.

For example, P2P simulators generally rely on delay-based models and forget about the underlying physical topology. Using this approach, tools such as PeerSim [START_REF] Montresor | PeerSim: A scalable P2P simulator[END_REF] can simulate platforms that scale up to millions of nodes. Yet, such models do not account for network contention, whereas most peers generally sit behind asymmetric DSL lines with very limited bandwidth. Although this kind of assumption may not be harmful when studying simple overlays and investigating the efficiency of look-up operations in a Distributed Hash Table (DHT), the use of such simulators for streaming operations and file sharing protocols is much more controversial.

This need for a scalable but accurate network representation is not specific to P2P studies. Many simulators in the High Performance Computing (HPC) community assume that bandwidth has been over-provisioned and that contention can be ignored. Although this assumption may hold true for supercomputers, it may not for commodity clusters or future exa-scale platforms where energy consumption is at stake, which precludes resource over-provisioning.

The common belief in the distributed computing community is thus that, when scale is at stake, simplistic network models have to be used. In this article, we propose an efficient platform representation that is the final piece missing to the opensource SIMGRID simulation toolkit to dismantle this belief by showing that reasonably accurate network models can be used at large scale. We show that, while using a much more accurate and complex network model, our simulations are as fast or even orders of magnitude faster than state-of-the-art simulators. Moreover, unlike other ad hoc simulators, the complete separation of application modeling from platform modeling enables SIMGRID based simulations to be evaluated seamlessly in a wide range of settings and to easily adjust the level of details to the scenario under investigation.

Section II details the main concerns related to network representation and modeling in a simulation context. Section III presents related work while Section IV exposes our proposal which is evaluated in Section V. We summarize our contributions and give some future work directions in Section VI.

II. MAIN CONCERNS ABOUT NETWORK REPRESENTATION AND MODELING IN DISTRIBUTED SYSTEM SIMULATION A. Community Specific Requirements

Generally speaking, simulation needs to account for key characteristics of the system under study, that heavily depend on the investigated scenario. Having a general discussion about network modeling without specifying the context of use would be meaningless. Researchers that study the effectiveness of a modification on a network protocol clearly require accurate packet-level simulations whereas a researcher interested in the scalability of a grid middleware involving very large data transfers over long periods of time would only require a coarse grain modeling of the network. Hence, we start by listing some very commonly investigated scenarios in distributed systems to illustrate the kind of phenomenon that one may wish to be accounted for.

P2P DHT simulation generally needs to account for the geographic diversity of peers, communication jitter, and peer churn. Most DHTs rely on the exchange of small messages and contention can thus be somehow ignored. Nevertheless the amount of exchanged messages is generally a measure of interest. A large amount of messages may indicate that the contention-free hypothesis is broken and that conclusions should be disregarded.

P2P streaming simulation is more complex as it involves a higher network traffic. The key characteristics to account for are network proximity, connection asymmetry (since peers act as forwarders) and interference between concurrent connections on the borders of the network. In such settings, a detailed modeling of the topology is not important. Only the edge of the network has to be accurately modeled, as it generally constitutes the main bottleneck.

Volunteer computing studies imply the simulation of clients and/or servers. The key characteristics to account for are the volunteer dynamic availability, properties (e.g., CPU speed, number of cores, disk space, . . . ), and reliability (regarding the correctness of the returned results). In some cases it may be important to model the characteristics of the connection of the peers to the Internet as well. Then the same requirements as for P2P streaming simulations apply.

High Performance Computing studies generally involve a complex communication workload made of sequences of very short communications, complex synchronization patterns, and structured concurrent transfers of large amount of data.

A faithful simulation of such workload requires a precise modeling of the network characteristics and protocols but can build on the regularity and homogeneity of the underlying network topology.

Grid Computing studies often involve numerous large data transfers across wide area networks that require an accurate modeling of contention and to account for both platform heterogeneity and hierarchy.

Cloud computing studies on IaaS may require a mixture of the previous requirements. For instance, it may be important to precisely model what happens within data centers. To reflect a hierarchical organization, high-end compute nodes are distinguished from low-end compute nodes and storage nodes. When the infrastructure comprises several sites, the wide area network connection between sites has also to be accounted for. Then it is possible to study the different charging mechanisms involved when going from one site to another. While a precise modeling of client connectivity may not be required, it is important to consider their geographic diversity at least.

All these scenarios illustrate a wide variety of needs for network modeling and representation. It partially explains why most simulators are domain specific.

B. Scalability Issues

The lack of interdisciplinary simulation approaches can also be explained by scalability requirements. To allow for studies at the desired speed and scale, most simulators build on and take advantage of the specifics of the scenarios they are designed for. When scalability is at stake, two related issues come into play that both involve space and time considerations:

• Platform description: Most simulators take a description of the platform as input. Its size depends on the expressiveness of the chosen description format. When some regularity in terms of topology or characteristics can be exploited, this description can be reduced to a minimal size and a program can turn this compact description into an appropriate memory representation. For instance, describing a homogeneous cluster or a set of peers whose speed is uniformly distributed does not require to detail each single entity. Such an approach greatly reduces both platform description size and parsing time. However, researchers often need to investigate complex scenarios to confirm or infirm hypothesis. Then details of the platform could be specified and modified at will, thus breaking these regularity assumptions. For such simulation scenarios a flat description of all components is needed, which greatly increases platform description size and parsing time.

• Memory representation: In most cases, flat descriptions are trivially translated into a flat representation leading to a large memory footprint. Even compact descriptions often have to be expended in memory. For instance, a homogeneous cluster of N machines can be solely described by N and the characteristics of one machine, e.g., CPU speed, latency, gap and overhead of the network. However, a simulator will have to keep track of the activity of every single machine. The size of the description would then be Θ(1)1 while its memory representation would be Ω(N ). The same occurs when describing a set of peers by a statistical distribution. Such expansion heavily impacts the parsing time. In some cases, the regularity can be preserved leading to a compact memory representation. For instance, in P2P DHT simulations, assuming that N peers are interconnected in a general tree topology implies that the platform description and data structure sizes are both in Θ(N ). This calls for a modular platform representation that allows researchers to express regularity when possible to help the simulator and adjust the level of details at will.

C. Network Communication Modeling

Research on networks has been relying on simulation for a long time, leading to standards and many popular opensource projects [START_REF] Cowie | Modeling the Global Internet[END_REF], [START_REF] Mccanne | The Network Simulator (ns2)[END_REF], [START_REF]The ns-3 Network Simulator[END_REF], [START_REF] Riley | Simulation of large scale networks II: large-scale network simulations with GTNetS[END_REF]. The validity is these tools is ensured by a wide usage and the cross reproduction of experiments. They simulate the entire protocol stack, i.e., each packet becomes an event. Then the simulation accuracy comes from a very fine modeling of the entire system. Unfortunately such simulations are very slow, hence limiting the scalability of studies on LSDC systems. Moreover, very fine models are not always meaningful at a very large scale. They require an instantiation with parameters that are often not available, such as a complete description of the Internet. At such scale, these models may be unstable and, badly instantiated, are worse than simple models. Then simulations of LSDC systems heavily rely on simpler models classified as follows:

• Delay-based. Representing the communication time by a constant delay or a statistical distribution is often sufficient. Such models account for heterogeneity but not for network proximity. Then many models determine delays based on coordinate-based systems [START_REF] Dabek | Vivaldi: A Decentralized Network Coordinate System[END_REF]. They are a good trade-off as they account for important characteristics with a Θ(N ) memory footprint and a O(1) delay computation time. Since coordinates may change over time and suffer from measurements issues, noise can be added to these coordinates. Similarly LogP-like models [START_REF] Culler | LogP: Towards a Realistic Model of Parallel Computation[END_REF], [START_REF] Hoefler | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF], [START_REF] Ino | LogGPS: a parallel computational model for synchronization analysis[END_REF] have been heavily used in HPC and are extremely scalable since both description size and delay computation time are in O(1). However, these very scalable models ignore network congestion and typically assume an extremely large bisection bandwidth.

• Contention-based. Modeling contention without hindering scalability requires an abstraction of the network topology that focuses on the most important parts. For instance, the bottleneck of a P2P streaming application will be mainly on the edge of the network. Contention in the core of the network may safely be ignored. Conversely, studying workload on data grids or collective communications requires a more precise model of the core of the network.

Simplistic packet-level simulation, e.g., store-and-forward or wormhole, of communications is blatantly inaccurate as it ignores many of the key characteristics of deployed protocols such as TCP. The obtained results are thus very questionable at best. Furthermore, such simulations are generally rather slow and not scalable since they involve a lot of simulation events for a single communication.

A sounder alternative is flow-level simulation in which the whole communication, or flow, is simulated as a single entity. The time needed to transfer a message of size S between hosts i and j is then given by:

T i,j (S) = L i,j + S/B i,j , (1)
where L i,j (resp. B i,j ) is the network latency (resp. bandwidth) on the route connecting i and j. Although determining L i,j may be easy, estimating the bandwidth B i,j is more difficult as it requires to account for interactions with every other flow. Then the simulation amounts to solving a bandwidth sharing problem, i.e., determining how much bandwidth is allocated to each flow. Given the computed bandwidth allocation,which defines all data transfer rates, and the size of the data to be transmitted by each flow, one can determine which flow will complete first. Upon completion of a flow, or upon arrival of a new flow, the bandwidth allocation can be reevaluated. Usually, this reevaluation is memory-less and does not depend on past bandwidth allocations. This approach makes it possible to quickly step forward through (simulated) time, and thus is attractive for implementing scalable simulations of LDSC systems with potentially large amounts of communicated data.

It has been shown in [START_REF] Velho | Accuracy Study and Improvement of Network Simulation in the SimGrid Framework[END_REF] that such models can account for the main characteristics of TCP connections. The slow start phenomenon models the fact that the TCP protocol does not send at full speed immediately and constantly adjust the emission rate to observed packet loss. Such mechanism breaks the linearity assumption of Eq. [START_REF] Montresor | PeerSim: A scalable P2P simulator[END_REF]. A clever instantiation leads to a very good approximation for large enough messages [START_REF] Velho | Accuracy Study and Improvement of Network Simulation in the SimGrid Framework[END_REF]. For small messages, very good results can be obtained with a piecewise linear model [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF].

The flow control mechanism of TCP is known to prevent full bandwidth usage as flows may be limited by large latencies [START_REF] Jain | The TCP Bandwidth-Delay Product Revisited: Network Buffering, Cross Traffic, and Socket Buffer Auto-sizing[END_REF]. Yet, it can be easily captured in a flow-level model by bounding the share a flow can get by the maximum congestion window size divided by the round trip time (RTT).

TCP is also known to be RTT-unfair. When two flows contend for bandwidth on a bottleneck link, they are assigned bandwidths inversely proportional to their RTTs [START_REF] Marfia | TCP-Libra: exploring RTT fairness for TCP[END_REF]. As demonstrated in [START_REF] Velho | Accuracy Study and Improvement of Network Simulation in the SimGrid Framework[END_REF], the RTT time needs to account both for latency along the path but also for the possibly low capacity of some links that may incur large delays. Such RTT values can then be used to decide how to share bandwidth amongst flows contending on a bottleneck link.

Finally, it is very common when sitting behind a DSL connection that upload traffic negatively impact download traffic, due to delayed acknowledgments. This phenomenon is known as ACK compression and also occurs on full duplex high speed Ethernet links directly connecting two machines. The observed poor link utilization may be explained by a data pendulum effect where data and ACK segments alternatively fill only one of the link buffers [START_REF] Heusse | Two-way TCP Connections: Old Problem, New Insight[END_REF]. A fluid model based on max-min sharing can easily model the impact of such cross traffic [START_REF] Velho | Flow-level Network Models: Have we Reached the Limits?[END_REF].

Recent and thorough validation studies in [START_REF] Velho | Accuracy Study and Improvement of Network Simulation in the SimGrid Framework[END_REF], [START_REF] Velho | Flow-level Network Models: Have we Reached the Limits?[END_REF] plead for carefully designed and instantiated fluid models as a very reasonable approximation for most LSDC systems. Although one may fear that such models are computationally expensive, bandwidth sharing can be computed in time linear with the number of connections and their interactions using sparse and efficient data structures [START_REF] Donassolo | Fast and Scalable Simulation of Volunteer Computing Systems Using SimGrid[END_REF].

D. Network Topology and Routing Representation

While an adequate representation should allow for an efficient extraction of all the necessary information to simulate communications, there exists some non-trivial trade-offs between information retrieval and representation size. The cost of representing network topology and routing can thus be decomposed in terms relative to execution time and data size. The execution time is made of the parsing time to build the data structure and the lookup time to retrieve a given route from this structure. Data size is reflected by both the size of the input, i.e., the description file provided by the user, and the memory footprint of the corresponding data structure.

Representation

Parsing Lookup Input Footprint

Flat N 2 1 N 2 N 2 Dijsktra N + E E + N log N N + E E + N log N Floyd N 3 1 N + E N 2 Clique N 2 1 N N 2 Star N 1 1 N Cloud N 1 N N
Let us consider a set of N nodes interconnected by a general graph with E edges. Table I summarizes the corresponding costs for most common network representations. For all of them, the lookup time is actually in Θ(route size) and we assume a static routing (although some of these representations support dynamic routing). In the flat representation, each route is completely defined by the set of equipments belonging to it. It can represent arbitrarily complex platforms (even something that would not be a graph) and routing. The main drawbacks of such a representation are its management cost and poor scalability [START_REF] Depoorter | Scalability of Grid Simulators : An Evaluation[END_REF]. The Dijkstra graph representation proposed in [START_REF] De Munck | Improving The Scalability of SimGrid Using Dynamic Routing[END_REF] only stores information on shortest paths and enables a better scalability. Shortest path routing is only slightly restrictive since most Internet protocols implement such a routing. Furthermore, this representation allows the simulator to recompute the routing for every communication and then to model dynamic routing. However, this memory scalability comes at the cost of a lookup time several orders of magnitude larger [START_REF] De Munck | Improving The Scalability of SimGrid Using Dynamic Routing[END_REF]. It can be reduced by adding caches, which are completely ineffective in scenarios that have poor locality or involve a very large number of entities. The Floyd graph representation, also proposed in [START_REF] De Munck | Improving The Scalability of SimGrid Using Dynamic Routing[END_REF], is another way to store information only on shortest paths with different time and space requirements. While this approach reduces the description size and has a very good lookup time, its parsing time and memory footprint are prohibitive. Finally, network graphs, such as clique, star graphs or "clouds" (where each peer is connected to the core of the network where contention is ignored), exhibit a regularity that can be exploited thanks to an ad hoc local routing table and a specific routing management.

III. RELATED WORK Many tools exist in the literature to simulate LSDC systems [START_REF] Montresor | PeerSim: A scalable P2P simulator[END_REF], [START_REF] Mccanne | The Network Simulator (ns2)[END_REF], [START_REF]The ns-3 Network Simulator[END_REF], [START_REF] Varga | An Overview of the OMNeT++ Simulation Environment[END_REF], [START_REF] Baumgart | OverSim: A Scalable and Flexible Overlay Framework for Simulation and Real Network Applications[END_REF], [START_REF] Taufer | SimBA: A Discrete Event Simulator for Performance Prediction of Volunteer Computing Projects[END_REF], [START_REF] Buyya | GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing[END_REF], [START_REF] Bell | OptorSim: A Grid Simulator for Studying Dynamic Data Replication Strategies[END_REF], [START_REF] Ostermann | GroudSim: An Event-Based Simulation Framework for Computational Grids and Clouds[END_REF], [START_REF] Calheiros | CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[END_REF], [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF]. Most comes from, and are limited to, a specific research community. Table II details how each tool addresses the concerns related to network modeling and representation. IV. PROPOSAL

A. Target Platform Characteristics

Most current distributed systems mainly rely on three types of possibly interconnected and mixed networks: System and Local Area Networks (SAN and LAN), National Research and Education Networks (NRENs), or privately and independently managed networks. Such networks are mostly interconnected in a hierarchical way.

System and local area networks are generally organized in a very hierarchical way (e.g., with fat trees) or with large switches. Most of the time, they locally manage routing based on shortest path algorithms that differ by distance estimation, i.e., distance vectors (delay or throughput), link states, or hybrid, and how they converge upon failures. However, failures are rare on local networks and the routing behavior is thus most of the time equivalent to shortest path determination (in number of hops).

Local networks use gateways, also named point of presence or network access point, to access to Internet Service Providers (ISPs) or NRENs, which are, in turn, connected to higher level networks at the scale of a continent. These high level networks are named backbone or tier-1 networks in the Internet terminology. They use their own routing policy, also based on shortest path. The Border Gateway Protocol (BGP) is the most deployed algorithm on the Internet.

From a performance point of view, higher hierarchy subnetworks may use traffic aggregation and dynamic routing to perform load balancing. However studies have shown that no change may occur for 80% of the paths in a 24 hour period [START_REF] Butler | Optimizing BGP security by exploiting path stability[END_REF]. Moreover, such changes may especially affect load balancing on backbone links, that are usually not communication bottlenecks. Then they can be ignored without any significant impact on simulation accuracy.

As a conclusion, large scale distributed systems are organized by a hierarchical aggregation of networks. Most aggregated networks are named Autonomous Systems (AS), as they behave independently from each other and may have very different structures. Each AS is connected with lower or higher level ASes by a set of entry points. This hierarchy is often bypassed by direct connections between same level ASes. Within an AS, a routing policy is applied, most of the time based on shortest path algorithms, e.g., OSPF or RIP.

B. Description Guidelines

Based on the aforementioned characteristics, we define a set of guidelines to build a satisfying network representation. First, the representation has to provide the user an easy way to directly describe the structure and entities he/she observes. Second, expressing hierarchy and composition of entities should be possible as it can reduce the simulation time. This expressiveness has to match community requirements from fine, e.g., router backplane, to coarse grain, e.g., cloud networks in P2P systems. Third, it should take advantage of the regular structures that exist in the network, such as cliques or stars, for sake of description simplicity. Fourth, a user should be able to specify that any AS can instantiate its own routing protocol. Finally, the path lookup and routing computation times should depend as less as possible on the size of the network to ensure a good scalability.

C. Proposal Representation Overview

None of the network routing representations presented in Section II-D exploits the hierarchy and the regularity of the platform. Each of them has its own pros and cons. The key to a scalable network representation is to provide users the ability to adapt the representation to their needs.

Our proposal is based on four semantic principles. First, we opt for static routing computation by default for scalability reasons. As stated in Section IV-A, it is sufficient for stable LSDC systems. Second, we use fluid models as they offer the best trade-off between accuracy and speed/memory footprint. Third, we take advantage of the structure of current large scale network infrastructures, thanks to the concept of AS, be they local networks or conform to the classical Internet definition. Last, we allow users to specify platform representation within each AS, which allows us to take advantage of the regular structure of an AS when possible.

We propose stock implementations of well known platform routing representations, such as Dijkstra, Dijkstra with cache, Floyd, Flat, and rule-based. The first four were described in Section II-D. The rule-based model relies on regular expressions to exploit regular structures. Figure 1 shows an example of such a hierarchical network representation.

Each AS has one or more gateways, which are used to compute routes between ASes included in an AS of higher level. With this mechanism, the simulator can determine routes between hosts belonging to different ASes by looking for the first common ancestor in the hierarchy (see Figure 2). Routing is then solved recursively using the hierarchy. It allows us to represent hierarchical platforms in a very compact and effective way. However, as real platforms are not strictly hierarchical, we also define bypassing rules to manually declare alternate routes between ASes. In addition to these semantic principles, we also define some syntactical principles. We define the network representation as an XML file, as it is a common and easy to handle format. A user can then use standard XML editors and advance features such as auto-completion, validation, and well-formed checking. We also define a set of tags that simplify the definition of regular ASes, such as homogeneous compute clusters, or peers. The cluster tag creates a set of homogeneous hosts interconnected through a backbone and sharing a common gateway. The peer tag allows users to easily create P2P overlays by defining at the same time a host and a connection to the rest of the world (with different upload and download characteristics and network coordinates). With such a tag we benefit both from the compactness of coordinate-based models that account for delay heterogeneity and correlation, and from the accuracy of fluid models for contention. As such, the Vivaldi [START_REF] Dabek | Vivaldi: A Decentralized Network Coordinate System[END_REF] and last-mile [START_REF] Beaumont | Using the Last-mile Model as a Distributed Scheme for Available Bandwidth Prediction[END_REF] models can be unified.

V. EVALUATION

We claim that our proposal drastically reduces memory footprint without implying any prohibitive computational overhead. We show that this approach competes in terms of speed and memory usage with state-of-the-art simulators from various domains while relying on much more accurate models that are generally considered as prohibitive. For each domain, we first define a classical simulation scenario. Then, we simulate this scenario with SIMGRID and the corresponding state-ofthe-art simulator to evaluate their respective scalability.

Experiments were conducted a single core of a node with two AMD Opteron 6164 HE 12-core CPUs at 1.7 GHz with 48 GB of memory. SIMGRID v3.7-beta, in which our proposal is integrated, was used. Source code, logs, platform files and analysis R scripts related to the experiments are freely available at http://simgrid-publis.gforge.inria.fr/xps/platform2011/. Table III exemplifies the flexibility and the compactness of our multi-purpose network representation proposal by giving the size of the XML input file in various scenarios.

A. Expressiveness

B. Volunteer Computing

In [START_REF] Donassolo | Fast and Scalable Simulation of Volunteer Computing Systems Using SimGrid[END_REF], we compared the performance of SIMGRID to that of SimBA. It is a discrete-event simulator that models hosts as finite-state automata with various parameters, i.e., compute, error, and timeout rates. Task failure or success depends on a uniform probability distribution while volatility is modeled using a Gaussian probability distribution. SimBA provides high scalability at price of simulation realism and is limited to the simulation of a single project. The SIMGRID implementation simulates the whole infrastructure and accounts for complex scheduling decisions on every client, network contention, and churn. Here, SIMGRID used the peer construct of Section IV-C and modeled host availabilities described by SETI@home traces from FTA [START_REF] Kondo | The Failure Trace Archive: Enabling Comparative Analysis of Failures in Diverse Distributed Systems[END_REF]. About one third of the simulation time was spent parsing these traces.

The execution times measured with our simulator and those reported by Estrada et al. in [START_REF] Taufer | SimBA: A Discrete Event Simulator for Performance Prediction of Volunteer Computing Projects[END_REF] are contrasted as follows. Both timings were obtained on a 3.0 GHz Intel Pentium 4 with 1GB RAM (the one initially used in [START_REF] Taufer | SimBA: A Discrete Event Simulator for Performance Prediction of Volunteer Computing Projects[END_REF]). Estrada et al. simulated 15 days of computation with 7, 810 hosts working on the Predictor@Home project in 107 minutes. SIMGRID simulates the same configuration in less than 4 minutes (for 10 runs the 95% confidence interval is [208. [START_REF] Marfia | TCP-Libra: exploring RTT fairness for TCP[END_REF]223.71] in seconds). Estrada et al. simulated 8 days of computation with 5,093 clients working on the CHARMM project in 44 minutes. SIMGRID simulates the same configuration in less than 90 seconds (for 10 runs the 95% confidence interval is [80.38, 80.87] in seconds).

While SimBA opts for many simplifications in its design and SIMGRID for more sophisticated but costly options (e.g., use of host availability traces or simulation of processes that execute arbitrary code), SIMGRID is still much faster.

C. P2P computing

Here we evaluate the impact of our proposal by comparing implementations of Chord simulations with various tools from the literature [START_REF] Montresor | PeerSim: A scalable P2P simulator[END_REF], [START_REF] Baumgart | OverSim: A Scalable and Flexible Overlay Framework for Simulation and Real Network Applications[END_REF] to an implementation on top of SIMGRID. Chord was chosen because it is representative of a large body of algorithms from the P2P community and already implemented in most P2P simulators.

Figure 3 reports the simulation timing of the Chord scenario as a function of the node amount. It compares the results of OverSim when using its internal simple and scalable network underlay, OverSim using a detailed packet-level network model based on OMNet++ [START_REF] Varga | An Overview of the OMNeT++ Simulation Environment[END_REF], and PeerSim to SIMGRID using flow-based [START_REF] Velho | Accuracy Study and Improvement of Network Simulation in the SimGrid Framework[END_REF] or simplistic delay-based network models. The largest scenario that we managed to run in less than 12 hours using OMNeT++ was 10, 000 nodes, in 1h40. With PeerSim, we managed to run 100, 000 nodes in 4h36 (but with a much lighter workload). With the simple underlay of OverSim, we managed to run 300, 000 nodes in 10h. With the precise flow-based model of SIMGRID, we ran 2, 000, 000 nodes in 6h43 while the simpler solely delay-based model of SIMGRID ran the same experiment in 5h30. Simulating 300, 000 nodes with the flow-based model lasts only 32 minutes. The memory usage for simulating 2 million nodes in SimGrid was about 36 GB, that represents 18 kB per node, including 16 kB for the user code stack.

These results show that SIMGRID is orders of magnitude more scalable than state-of-the-art P2P simulators. It is 15 times faster than the fastest ones, and simulates scenarios that are ten times larger. This trend remains when using the precise flow-based model, while simulation accuracy is improved.

D. High Performance Computing

In this section, we compare our proposal to the results published in [START_REF] Hoefler | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF]. LOGGOPSIM is a recent simulator specifically tailored for the study of MPI programs on large-scale HPC systems. It builds on the LogGPS model [START_REF] Ino | LogGPS: a parallel computational model for synchronization analysis[END_REF], which is a delay-based model accounting for middleware overhead and hardware gaps that prevent a perfect sustained usage of network cards. As explained in [START_REF] Hoefler | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF], the LogGPS model "ignores congestion in the network and assumes full effective bisection bandwidth", which is a valid hypothesis for several high-end computing platforms but not for cheaper Ethernet clusters or even torus-based networks as used in BlueGene or Cray machines. The model used in SIMGRID is an extension of the one proposed in [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF] and accounts for such phenomenon as well as for network contention occurring in the core of the network. The importance of accounting for such phenomenon was demonstrated in [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF] for MPI collective operations involving large amounts of data. LOGGOPSIM represents MPI executions as GOAL traces, i.e., DAGs of computations and communications. SIMGRID supports the evaluation DAG scheduling algorithms through the SIMDAG API since 2001. We aimed at comparing our proposal with LOGGOPSIM in the very same experimental setting used in section 4.1.2 of [START_REF] Hoefler | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF], i.e., the execution of a binomial broadcast on various the number of processes. Unfortunately, the input GOAL traces used in [START_REF] Hoefler | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF] were not available. Then we have compared our simulation results to the published one instead of reproducing the experiments with LOGGOPSIM. The evaluation of LOGGOPSIM was done on a 1.15 GHz Opteron workstation with 13 GB of memory. To perform a comparison as fair as possible we scaled down frequency of our processor down to 1GHz. Figure 4 shows the results. While using significantly more elaborate platform and communication models, and thus producing more meaningful results, SIMGRID is only roughly 75% slower than LOGGOPSIM. This demonstrates that scalability does not necessarily comes at the price of realism (e.g., ignoring contention on the interconnect). The genericity of SIMGRID data structures comes at the cost of a slight overhead since our memory usage for 2 23 processors is 15GB, which is slightly larger than what is achieved in [START_REF] Hoefler | LogGOPSim -Simulating Large-Scale Applications in the LogGOPS Model[END_REF]. Yet, we think this loss is reasonable and amply offset by the gain in flexibility.

E. Grid computing

In this section we compare to GRIDSIM [START_REF] Buyya | GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing[END_REF] (version 5.2 released on Nov. 25, 2010), a tool used widely in the research community. The scenario we propose is a simple master worker setting in which the master distributes N fixed size jobs to P workers in a round-robin way. In GRIDSIM, we did not define any network topology, hence only the output and input baud rate are used to determine transfer speed. For SIMGRID, we use a model of the Grid 5000 platform [START_REF]Grid'5000[END_REF] (10 sites, 40 clusters, 1500 nodes), modeling each cabinet of the clusters as well as the core of the wide area network interconnecting the different sites. The experiments were conducted using an Intel Xeon Quadcore 2.40GHz with 8GiB of RAM.

The number of tasks n task to distribute was uniformly sampled in the [1; 500, 000] interval and the number of workers W was uniformly sampled in the [100; 2, 000]. We tried larger range at first but we faced the same scalability issue as already mentioned in [START_REF] Depoorter | Scalability of Grid Simulators : An Evaluation[END_REF]: GRIDSIM cannot run for more than 10,000 hosts because of Java thread management issues. We performed 139 such experiments for GRIDSIM (1000 for SIMGRID as it was much faster) and measured the wallclock time T (in seconds) and the memory consumption M (in kB). These experiments prove that T GRIDSIM is quadratic in n task and linear in W . As expected, the size (input, output and amount of computation) of the tasks to distribute have no influence, hence the following model (the R 2 of the linear regression is 0.9871):

T GRIDSIM ≈ 5.599 10 -2 W + 1.405 10 -8 n 2 task Surprisingly, the memory, is not a simple polynom in W and n task . It seems to be piecewise linear in both W and n task (with a very steep slope at first and then a less steep one). Furthermore there are a few outstanding points exhibiting particularly low or high memory usage. All this can be probably explained by the garbage collection of Java. Hence, we only report the behaviour for the situation where the number of tasks is larger than 200,000 and the slope is not steep, taking care of removing a few outliers (R 2 =0.9972):

M GRIDSIM ≈ 2.457 10 6 + 226.6W + 3.11n task Conducting the same analysis for SIMGRID shows that it is much more stable and requires a much smaller time and memory footprint (R 2 equal to 0.9984 and 1 respectively):

T SIMGRID ≈ 1.021 10 -4 W + 2.588 10 -5 n task M SIMGRID ≈ 5188 + 79.9W

This means that 5.2Mb are required to represent the Grid 5000 platform and the internals of SIMGRID. We did not optimize the stack size of processes (unlike when simulating P2P scenarios), which is why we have a payload of 80K per worker. Last, since tasks are allocated and deallocated on the fly, there is no visible dependency on n task .

This clearly indicate that SIMGRID (with a flow-based network model and a very detailed network topology) is several orders of magnitude faster and smaller in memory than GRIDSIM (with a delay-based model and no network topology). To illustrate the time and memory scalability, the previous regressions indicate that GRIDSIM requires more than an hour and 4.4 GB for N = 500, 000 and P = 2, 000 while SIMGRID requires less than 14 seconds and 165MB.

VI. CONCLUSION AND FUTURE WORKS

In this paper, we reviewed existing approaches to represent large scale distributed computing systems in a simulation context. We characterized the underlying problem of the network representation and proposed an original and efficient multi-purpose representation. Our experiments showed that our approach is far more scalable than what is done by state-of-theart simulators from any of the targeted research communities. We integrated this network representation into the SIMGRID tool. The chosen hierarchical and adaptive description based on the concept of Autonomous Systems also allows us to combine different kinds of platforms, e.g., a computing grid and a P2P system, to broaden the range of simulation possibilities.

We also demonstrated that the widespread beliefs that scalable simulations necessarily imply to simplify the network models and avoid the use of threads are erroneous. Our implementation within SIMGRID does not trade accuracy and meaning for scalability and also allows its users to simulate complex applications.

As future work we aim at considering the specifics of emerging systems such as IaaS Clouds. We also plan to further reduce platform description size (and hence parsing time) and memory footprint by exploiting stochastic regularity when available and by improving the programmable description approach. One particularly promising approach would be to inject randomness directly into the platform description, to model host availability or peer characteristics for instance.

Figure 1 .

 1 Figure1. Illustration of hierarchical network representation. Circles represent processing units and squares represent network routers. Bold lines represent communication links. AS2 models the core of a national network interconnecting a small flat cluster (AS4) and a larger hierarchical cluster (AS5), a subset of a LAN (AS6), and a set of peers scattered around the world (AS7).

Figure 2 .

 2 Figure 2. Main steps of the hierarchical routing mechanism.

Figure 3 .

 3 Figure 3. Running times of the Chord simulation with constant and precise network models on SIMGRID, compared to Oversim with a simple underlay, OMNeT++ and PeerSim.

Figure 4 .

 4 Figure 4. Performance comparison of LOGGOPSIM and SIMGRID when simulating a binomial broadcast.

Table I Θ

 I COMPLEXITY OF NETWORK ROUTING REPRESENTATIONS.

Table II SIMULATION

 II TOOLS ANSWERS TO NETWORK CONCERNS.

		Community Input	Memory Network model	Routing
	NS-2	Network	API	flat	packet-level	static
	NS-3	Network	API	flat	packet-level	static
	Omnet++	Network	text	hierarchical packet-level	static,dynamic
	PeerSim	P2P	API	cloud	delay-based	static (direct)
	OverSim	P2P	API	cloud	delay-based	static (direct)
	SimBA	VC	text	none	delay-based	none
	LOGGOPSIM HPC	text	cloud	delay-based	static (direct)
	GridSim	Grid	API	flat	delay-based	none
	OptorSim	Grid	Text file	flat	contention-based	short. path
	GroudSim Grid,Cloud	API	cloud contention-based	static (direct)
	CloudSim	Cloud Brite, API	flat	delay-based dynamic (short. path)
	SIMGRID	LSDC XML, API	flat	Fluid	static (indirect)

Table III SIZE

 III OF PLATFORM DESCRIPTION FILE IN VARIOUS SCENARIOS.

	Community	Scenario	Size
	P2P	http://pdos.csail.mit.edu/p2psim/kingdata/	209KB
	P2P	http://www.cs.cornell.edu/People/egs/meridian/	301KB
	P2P	http://www.eecs.harvard.edu/ ∼ syrah/nc/	28KB
	Grid	10 sites, 40 clusters, 1500 nodes	22KB
	HPC	4096 clusters of 64 nodes	27MB
	Cloud	3 small data centers + Vivaldi	10KB

Or Θ(log(N )) if we count the bytes needed to describe N . In the remaining, we omit this log(N ) factor in all our complexity estimation as it is relatively negligible for the platform sizes we consider.

ACKNOWLEDGMENTS

This work is partially supported by ANR (Agence National de Recherche), project reference ANR 08 SEGI 022 (USS SIMGRID) and ANR 11 INFRA 13 (SONGS). Special thanks to INRIA, which supported David Marquez's internship.