Cláudio Carvalho

Jonas Costa

Raul Lopes

Ana Karolinna

Nicolas Nisse

Cláudia Linhares Sales

¶ Cláudia

Linhares Sales

From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows

Keywords: Digraphs, Branchings, Branching flows, Arc-disjoint flows

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Let D = (V, A) be a digraph. If e is an arc of D from a vertex v to a vertex w, we may refer to e as vw. The in-degree of a set X ⊆ V (D), denoted by d - D (X), is the number of arcs with tail outside of X and head inside of X. If X = {v}, we simply write d - D (v) instead of d - D ({v}) (omitting braces). For an integer n, we denote by [n] the set {1, . . . , n}.

A network N = (D, u) is formed by a digraph D = (V, A) with a capacity function u : A(D) → Z + . If all arcs in D have capacity λ, we simply write u ≡ λ. A flow in N is a function f : A(D) → Z + such that f (vw) ≤ u(vw), ∀vw ∈ A(D) (note that contrary to the classical definition of flows, there is no need to satisfy the conservation constraints). For a vertex v ∈ V (D), we define f + (v) = vw∈A f (vw) and f -(v) = wv∈A f (wv), that is, f + (v) and f -(v) are the amount of flow leaving and entering v, respectively. The balance vector of a flow f in a network N = (D, u) is the function b f : V (D) → Z associating each vertex v ∈ V (D) to the value f + (v) -f -(v). If b f (v) = , we may also say that v has balance . A vertex s ∈ V (D) is a source of f if f + (v) > 0 and f -(v) = 0. An (s, t)-cut on a network N = (D, c) is a bipartition (S, S = V (D) \ S) of V (D) such that s ∈ S and t ∈ S. The capacity of an (s, t)-cut is the sum of the capacities of arcs with tail in S and head in S and it is denoted by u(S, S). For other concepts on graphs and digraphs, we follow standard terminology as in [START_REF] Bang-Jensen | Digraphs: theory, algorithms and applications[END_REF][START_REF] Bondy | Graph theory[END_REF].

Flows are widely studied as they allow, with a certain elegance and simplicity, modeling problems in different areas of study such as transportation, logistics and telecommunications. In the theoretical field, they are used to solve various problems in graphs and digraphs. A long list of results related to flows can be found in [START_REF] Ahuja | Network flows : theory, algorithms, and applications[END_REF][START_REF] Ford | Flows in Networks[END_REF]. In this work, we deal with one variation of the problem where, roughly speaking, k arc-disjoint flows, having in common the same source and with a prescribed balance vector, have to be found.

Since a flow in a network can be entirely described by its associated balance vector, the goal of a flow problem can be seen as finding a flow f whose balance vector respects a given set of properties. Therefore, the problem that has been considered is: given a digraph D together with a balanced vector b : V (D) → Z, does there exist a flow f in D such that b f = b? For example, in the decision version of the classical MAXIMUM FLOW problem we are given a network N = (D, u) together with a positive integer k and a pair of vertices s, t ∈ V (D), and the goal is to decide if N admits a flow f with b f (s) ≥ k such that b f (v) = 0 for all v ∈ V (D) \ {s, t} and b f (s) = -b f (t). Such a flow f is known as an (s, t)flow and, in this case, we say that f has value b f (s). This problem can be solved in polynomial time [START_REF] Ford | Maximal flow through a network[END_REF] (see [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]Chapter 10] for a survey on algorithms for MAXIMUM FLOW). Furthermore, by applying a simple reduction to MAXIMUM FLOW (see [START_REF] Bang-Jensen | Digraphs: theory, algorithms and applications[END_REF]Lemma 4.2.2]), we can solve in polynomial time any flow problem in which the aim is to find a flow g with v∈V (D) b g (v) = 0.

The possibility of considering the coexistence of flows respecting some properties in a network gives more power of modeling for this already useful tool. In [START_REF] Even | On the complexity of timetable and multicommodity flow problems[END_REF], a more general version of the flow problem was investigated. There, the goal was to find a collection of (s i , t i )-flows that sum to a specific value r and such that the sum of all the flows in each arc respects its capacity. It was shown that this version of the problem is NP-hard since it generalizes many hard problems in the literature, including the notoriously hard DIRECTED DISJOINT PATHS problem.

Two flows f and g in a network N = (D, u) are arc-disjoint if f (vw) • g(vw) = 0, ∀vw ∈ A(D). In [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF], the problem of finding arc-disjoint flows was introduced and studied. The authors considered many constraints showing that some generalize important problems, known to be hard, and that there are cases where polynomial-time algorithms are possible. Amongst other results, they showed that the following are NP-complete: the problem of deciding if there are two arc-disjoint flows in a network where all arcs have capacity one, the problem of deciding if there are two arc-disjoint flows with the same balance vectors in a network where all arcs have capacity at most 2, and the problem of deciding if there are two arc-disjoint (s, t)-flows in a network where all arcs have capacity at most two.

We say that a digraph D is an s-branching if there is a directed path from s to every other vertex in D and the underlying (i) graph of D is a tree. We also say that D has root s. There is an extensive literature concerning the study of branchings (see for example chapter 9 of [START_REF] Bang-Jensen | Digraphs: theory, algorithms and applications[END_REF]), given their relevance both from practical and theoretical point of view due to its numerous applications, some of which we enumerate below. A classical result by Edmonds [START_REF] Edmonds | Edge-disjoint branchings[END_REF] characterizes the digraphs containing k arc-disjoint s-branchings and later proofs of the same theorem done in [START_REF] Lovász | On two minimax theorems in graph[END_REF][START_REF] Tarjan | A good algorithm for edge-disjoint branching[END_REF] show polynomial-time algorithms to find such branchings if they exist.

Theorem 1 (Edmonds' branching theorem [START_REF] Edmonds | Edge-disjoint branchings[END_REF]).

A digraph D = (V, A) has k arc-disjoint s-branchings if and only if d - D (X) ≥ k for all X ⊆ V (D) \ {s} with X = ∅.
A stronger version of this result, allowing each branching to have its own set of roots, can be seen in [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]Chapter 53]. There are many applications for Edmonds' Theorem on arc-disjoint branchings: it can be used, for example, to prove Menger's Theorem [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF], to characterize arc-connectivity [START_REF] Shiloach | Edge-disjoint branching in directed multigraphs[END_REF], and to characterize branching cover [START_REF] Frank | Covering branchings[END_REF]. The problem of finding disjoint branchings was recently studied in the setting of temporal graphs in [START_REF] Marino | Edge-disjoint branchings in temporal graphs[END_REF]. In this paper, we consider branchings in terms of flow.

An s-branching flow in a network

N = (D, u) is a flow f such that b f (s) = n -1 and b f (v) = -1 for every v ∈ V (D) \ {s}.
In other words, f reaches all vertices of D and each vertex other than s retains one unit of flow. Here, we study the problem that, given a digraph D and a source s and an integer k, aims at deciding whether there exist k arc-disjoint s-branching flows.

Related work: Finding one s-branching flow in a given network is easy: since v∈V (D) b f (v) = 0, we can reduce this problem to the problem of finding one (s, t)-flow, as discussed above. We can also find k arc-disjoint s-branching flows in polynomial time when u ≡ n -1. In [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF] it was shown that, in this case, N admits an s-branching flow if and only if D contains an s-branching. Thus, applying Theorem 1, the authors provided a characterization of networks admitting k arc-disjoint s-branching flows, which are exactly the networks constructed on digraphs containing k arc-disjoint s-branchings. They also provided a polynomial time algorithm that finds such flows if they exist. We now discuss how the tractability of this problem, in general, depends on the choice of the capacity function.

In [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF], the authors showed that the problem of deciding if a network has k arc-disjoint s-branching flows is NP-complete if every arc has capacity at most two, and in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] this result was extended to networks with capacity at most , for every fixed ≥ 2. For most choices of larger capacities, the problem remains hard. In [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] it was shown that, unless the Exponential Time Hypothesis [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF] fails, there is no polynomial time algorithm for the problem of finding k arc-disjoint s-branching flows in a network N = (D, u) with u ≡ λ for any choice of λ such that n/2 ≤ λ ≤ n -(log n) 1+ε , ε > 0, even if D is acyclic. In [START_REF] Costa | Um estudo de redes com fluxos ramificados arco-disjuntos[END_REF] the authors adapted this last proof to show that the same holds if (log n) 1+ε ≤ λ ≤ n/2. The last two results have an intersection point, which is when u ≡ n/2. The two constructions result in the same network in this case, and it is worth noticing that it gives a polynomial time reduction. So, for u ≡ n/2, the problem is NP-hard. On the positive side, in [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF] it was also shown that the problem is solvable in polynomial time when λ = n -c, for fixed k and c ≥ 1. More precisely, the authors showed that the problem is XP for fixed k and c when the goal is to find k arc-disjoint s-branching flows. This was later improved to an FPT algorithm with the same parameter in [START_REF] Bessy | FPT algorithms for packing k-safe spanning rooted sub(di)graphs[END_REF].

In short, the results presented in the previous paragraph roughly say that the problem of deciding if a given network with u ≡ n -c contains k arc-disjoint s-branching flows admits a polynomial time algorithm for every fixed c ≥ 1, and is unlikely to admit such an algorithm for most other choices of u under reasonable complexity hypothesis. Thus, any general characterization of networks admitting such flows must also be hard to verify. In the following, we extend to s-branching flows the property characterizing networks containing k arc-disjoint s-branchings, which was originally proposed in [START_REF] Costa | Um estudo de redes com fluxos ramificados arco-disjuntos[END_REF], .

For a vertex s ∈ V (D) and two non-negative integers k, λ, we say that

D is (k, λ, s)-sufficient if, for every X ⊆ V (D) \ {s} with X = ∅, we have d - D (X) ≥ k |X| λ . (1)
If N = (D, u) with u ≡ λ is a network constructed on such a digraph, we may also say that N is (k, λ, s)-sufficient.

It is not hard to visualize the relationship between this property and the one in the statement of Theorem 1: if λ = n -1, then every arc of D has enough capacity to send as many units of flow as needed to reach any set X ⊆ V (D). Thus, capacities are not an issue and Inequality 1 states that d - D (X) ≥ k, as in Theorem 1, since |X| ≤ n -1. For other choices of λ, note that every s-branching flow on N must reach a set of vertices X with at least |X| units of flow to cover it. Thus each s-branching flow in N uses at least |X|/λ arcs to cover X. More formally, the following was proved.

Proposition 1. [7] Let N = (D, u) be a network with u ≡ λ and s ∈ V (D). If N admits k arc-disjoint s-branching flows, then D is (k, λ, s)-sufficient.
Our contributions: In Section 2, we show how to construct a family of a (k, λ, s)-sufficient networks not containing k arc-disjoint s-branching flows. On the positive side, we show that some positive cases of sufficiency do occur depending on the structure of D and on the choice of k and λ.

In Section 3, we show that (k, λ, s)-sufficiency guarantees the existence of k arc-disjoint s-branching flows in a network N = (D, u) when D is an s-branching where parallel arcs are allowed, and when D is a collection of internally disjoint multi-paths starting at s and all ending on the same vertex t ∈ V (D). In other words, the flows are guaranteed to exist when the underlying simple graph of D is a tree or a spindle, and thus the considered property characterizes the existence of the flows in those classes of networks. Additionally, we show that we also have this guarantee in general digraphs when k = 1, when λ = 1, and when λ = |V (D)| -2. Finally, we show that, for a network N = (D, u) with u ≡ λ and an integer p

satisfying pλ ≥ n -1, if d - D (X) ≥ pk for all non-empty X ⊆ V (D) \ {s}, then N admits k arc-disjoint s-branching flows.
In Section 4, we show that the analyzed property is not enough to improve the tractability of the problem of finding the desired flows. Namely, we show that it is NP-complete to decide if a network N admits k arc-disjoint s-branching flows even if its underlying simple graph is constructed by appending a path to the end of a spindle and we know beforehand that N is (k, λ, s)-sufficient. Since this property can be easily verified in this class and it is always necessary for the existence of the flows, it is no surprise that it is not enough to guarantee the existence of the k arc-disjoint s-branching flows.

In Section 5 we close the paper with some open questions. We remark that polynomial time algorithms to find the flows can be extracted from the provided constructive proofs of the aforementioned results.

2 Networks on (k, λ, s)-sufficient digraphs not containing the flows

In Figure 1 we give an example of a (2, n -3, s)-sufficient network that does not contains 2 arc-disjoint s-branching flows, and we show that it can be generalised to (2, n -c, s)-sufficient networks, for every fixed c ≥ 3 (Theorem 2). Thus the best that we can expect is that every (2, n -2, s)-sufficient network contains the desired s-branching flows. In Section 3 we show that this is indeed true for general networks (c.f. Theorem 9).

If |X| ≤ n -c, then we must show that d -(X) ≥ 2 |X| n-c = 2. If a > 0, one can see that there are two arcs entering X ∩ A, then d -(X) ≥ 2 + b ≥ 2. Otherwise, we have that b > 0 and d -(X) = 2b ≥ 2. If |X| > n -c, then we must show that d -(X) ≥ 2 |X| n-c = 4. Note that in this case a > 0 and b ≥ 2. So, we have d -(X) ≥ 2 + b ≥ 4.
Now we show that N does not admit 2 arc-disjoint s-branching flows. Observe that each flow can use at most one arc from A to B, by the size of A and the capacity of the arcs (specially the arcs leaving s to A). So, there is a vertex v in B that must be reached by each flow through an arc coming from s, but there is only one arc from s to v.

Next, we show how to construct a family of (k, λ, s)-sufficient networks that do not contain k arcdisjoint s-branching flows.

Theorem 3. For all λ ≥ 2 and for all even k ≥ 2, there exists a (k, λ, s)-sufficient network N = (D, u), with u ≡ λ, that does not admit k arc-disjoint s-branching flows.

Proof: Given an even k ≥ 2 and λ ≥ 2, start the construction of N by adding the vertices s, a, b, c and d then add an arc from s to every other vertex along with the arcs ab, ac, bd, and cd. Subdivide the arc bd (cd) λ-2 times and let B (C) be the union of {b} ({c}) and the set of vertices obtained by the subdivisions of bd (cd) (note that if λ = 2 nothing changes at this step, which means that B = {b} and C = {c}), and then double the arcs between vertices of B (C). Let P be a path with λ vertices and denote by e and f , respectively, the first and last vertex of P . Triple the first λ -2 arcs of P and double the last one (the one that enters f ). After that, add P to D along with the arcs de, f a and two parallel arcs se. To complete the construction, replace each arc by k/2 copies of itself and set u ≡ λ. See Figure 2. Here, we say that a set

X ⊆ V (D) is satisfied if d - D (X) ≥ k |X|/λ .
To prove that D is (k, λ, s)-sufficient, we consider the case where k = 2 because for a larger k we multiply the in-degree of each subset of V (D) -s by k/2. Observe that, except for s, every vertex has in-degree at least 2 in D and that for every X ⊆ V (D) -s each vertex from {a, b, c, d} which belongs to X sums at least one unit to its in-degree and the vertex e sums to two. Consider a set X ⊆ V (D) -s. If D[X] has a cycle, then d - D (X) ≥ 5, once X necessarily contains a, d, P and either B or C (or both), but its also true that |X| ≥ 2λ + 1, which means that should be at least one extra arc entering in X for it to be satisfied. To verify the existence of this extra arc assume without loss of generality that B ⊂ X (the case where C ⊂ X is symmetric) and take the longest (z, d)-path in D[X] such that z ∈ C. If no such path exists, there is at least one arc going from C to d which was not counted before and if the path exists, then either z = c or the two arcs yz enters X, where y is the in-neighbor of z which, by the choice of z, cannot be in X. Now consider that D[X] is acyclic. Note that each source in D[X] contributes with at least two units in the in-degree of X. Since each weak component of D[X] has at least one source, then every X with |X| ≤ λ is satisfied. Similarly, the same also holds when λ < |X| ≤ 2λ if D[X] has more than one weak component or only one component with many sources. Otherwise D[X] has only one weak component W with a single source w, and we have 5 cases:

• w ∈ B. Observe that in this case {d, e} ⊂ X, once that |X| ≥ λ + 1 and |B| = λ -1, which means that d - D (X) ≥ 5.

• w ∈ C. It's analogous to the previous one.

• w = a. In this case, there are at least two vertices from {b, c, d} in X. That is, d -(X) ≥ 4.

• w = d. If d is the source, then e ∈ X, and thus d - D (X) ≥ 5. • w ∈ V (P ). Except for f , every vertex of P has in-degree three and since X must contains a, then d - D (X) ≥ 4. When w = f , besides a, X must also contains at least one vertex from {b, c} which guaranties d - D (X) ≥ 4. When 2λ + 1 ≤ |X| ≤ 3λ, the in-degree of X must be at least 6. We start with the case that D[X] has just one weak component. If w is a source in D[X], again we have 5 subcases:

• w ∈ B. In this case, since |B∪{d}| = λ, either there is a vertex in C which is also a source in D[X] or a ∈ X. In both situations, d, e ∈ X because |B ∪ C| < 2λ. Thus, d - D (X) ≥ 6. • w ∈ C. It's analogous to the previous one.

• w = a. Once |{a, d} ∪ B ∪ C| = 2λ, if a is a source, there is a path in D[X] that starts in a, goes through B or C, d and ends in some vertex of P .

• w = d. When d is a source, for sure {a, b, c, d, e} ⊂ X.

• w ∈ V (P ). Here, in order to avoid cycles, we know that if w = f , necessarily a, b, c and d are also included in X and if w = f , at least a, b and c are included in X but, in this case, w already contributes with 3 for the in-degree of X. Thus d - D (X) ≥ 6. If D[X] has more than 2 weak components, we already know that d - D (X) ≥ 6. If D[X] has two weak components Y, Z, one of them, say Y , has at least λ + 1 vertices and hence, as in the previous cases,

d - D (Y ) ≥ 4. Thus, d -(X) ≥ 6.
Notice that if there are k arc-disjoint s-branching flows x 1 , x 2 , . . . , x k in N , as d - D (B) = d - D (C) = k, each one of these k arcs has to be used by a different flow, and carry at least λ -1 units of flow, that is, one unit for each vertex of B and C. Now observe that k/2 of the arcs which enter in B come from a and the same for the ones that enter C, and then a must receive λ units of flow on each of it's k incoming arcs in order to send the proper amount of flow to B and C. Assume without loss of generality that the k/2 copies of sa are going to be used by x 1 , x 2 , . . . , x k/2 and the k/2 copies of f a are left for x k/2+1 , x k/2+2 , . . . , x k . Since the in-degree of f is also equal to k, f can receive at most λ units of flow of each x 1 , x 2 , . . . , x k and hence it can send at most λ -1 units of any of these flows to a. Therefore, N does not admit k arc-disjoint s-branching flows.

Networks on (k, λ, s)-sufficient digraphs containing the flows

In this section, we show some positive results regarding (k, λ, s)-sufficiency. We remark that the constructive proofs of those results can be naturally adapted to polynomial-time algorithms to find the desired flows in those networks.

We say that a digraph D = (V, A) is a multi-branching if D is an out-branching when we ignore its parallel arcs and, for ≥ 1, we denote by D the class of multi-spindles. That is, the class of digraphs formed by a source vertex s, a sink vertex t, pairwise internally vertex-disjoint multi-paths P 1 , . . . , P from s to t, each with p i ≥ 1 internal vertices, 1 ≤ i ≤ , respectively. See Figures 3(a The following result is useful for proving Theorem 4.

Lemma 1. Let D be a (k, λ, s)-sufficient digraph and let W be a nonempty subset of

V (D) \ {s} such that N + D (V (D) \ W ) = {w}, w ∈ W . Then D[W ] is (k, λ, w)-sufficient.
Proof: Since w is the unique vertex of W which has in-neighbours in V (D)\W , then we have

d - D[W ] (v) = d - D (v) for every v ∈ W \ {w}. Thus, for every X ⊆ W \ {w} we have d - D[W ] (X) = d - D (X).
Proof of Theorem 4: We are going to use induction on the height h of the multi-branching D with root s to construct k arc-disjoint s-branching flows f 1 , f 2 , . . . , f k in N . The base case is h = 1. In this case D is a star and, since it is (k, λ, s)-sufficient, there are at least k arcs from s to every other vertex and we can use one arc for each flow f j , for j ∈ [k].

Induction step: Suppose that the statement holds for multi-branchings of height h < q. Assume that D has height q and let r 1 , r 2 , ..., r p be the out-neighbours of s in D.

Let B ri be the subgraph of B s that is a multi-branching with root r i , for each i ∈ [p]. Observe that, by Lemma 1, B ri is (k, λ, r i )-sufficient and has height h i ≤ q -1, thus, by induction hypothesis, B ri

has k arc-disjoint r i -branching flows f i 1 , f i 2 , . . . , f i k . We know that d -(r i ) ≥ k |Br i | λ
and then we can use

|Br i | λ
of these arcs to send the proper amount of flow from s to r i on each x j to complete the k s-branching flows.

Since a multi-path is also a multi-branching, Theorem 4 generalizes the result of [START_REF] Costa | Um estudo de redes com fluxos ramificados arco-disjuntos[END_REF] for multi-paths. Proof: Let D be a digraph in D that is (k, λ, s)-sufficient. By definition, D is composed by the multipaths P 1 , P 2 , . . . , P and V (P i ) ∩ V (P j ) = {s, t} for every 1 ≤ i < j ≤ . We denote the p i internal vertices of

P i by v i pi , v i pi-1 , . . . , v i 2 , v i 1 in this order, for every i ∈ [ ]. For every j ∈ [p i ], we define r i j ≥ 0 so that d - D (v i j ) = k j/λ + r i j . Remark that d - D (v i j ) ≥ k j/λ , otherwise the set {v i j , v i j-1 , . . . , v i 1 }
would contradict the fact that D is (k, λ, s)-sufficient, since the only arcs entering in it are those arriving at v i j . Considering only the vertices with an index multiple of λ, that is, the vertices v i jλ for every 1 ≤ j ≤ p i /λ , let

r(P i ) = k, if p i < λ, min{r i jλ | 1 ≤ j ≤ p i /λ }, otherwise. For all i ∈ [ ],
we define e i as the number of arcs from v i 1 to t and m i = min{r(P i ),

e i }. Let k = i=1 m i .
Assume without loss of generality that P 1 , P 2 , . . . , P q are the paths on which r(P i ) ≤ e i , for i ∈ [ ]. Then k = q i=1 r(P i ) + i=q+1 e i . Now, for every i ∈ [q], we choose a

j i ∈ [ p i /λ ] which satisfies d - D (v i jiλ ) = kj i + r(P i ) and we define X i = {v i jiλ , v i (jiλ)-1 , . . . , v i 1 }. Consider the set X = q i=1 X i ∪ {t}. We have that d - D (X) = q i=1 d - D (X i ) + i=q+1 e i = k q i=1 j i + q i=1 r(P i ) + i=q+1 e i = k q i=1 j i + k . ( 2
)
Since D is (k, λ, s)-sufficient and

|X i | = j i λ d - D (X) ≥ k |X| λ = k 1 λ + λ q i=1 j i λ = k q i=1 j i + k. (3)
Combining ( 2) and ( 3) we conclude that k ≥ k. To finally construct the k arc disjoint branching flows, we need the following claim. Claim 1. There are k arc-disjoint flows x i 1 , . . . , x i k on the network N i = (P i , u), with u ≡ λ, such that x i 1 , . . . , x i mi are branching flows in N i and x i mi+1 , . . . , x i k are branching flows in N i -t. Proof. We show how to construct the flows x i 1 , x i 2 , . . . , x i k . For every j ∈ [p i ], the vertex v i j must receive j +1 units of flow on the first m i flows and j units on remaining k -m i flows. Since d - D (v i j ) = d - Pi (v i j ) ≥ k j/λ , we can use a distinct group of j/λ arcs to send j units of flow on each one of the k flows and we only have to argue how to send the extra unit for the flows x i 1 , . . . , x i mi . If j is a multiple of λ, then there are at least another r(P i ) extra arcs entering v i j and since m i ≤ r(P i ) they can be used to send the extra units (note that, if r(P i ) = 0 then m i = 0 and no extra unit is needed). Otherwise, j is not multiple of λ and when we send j units of flow through j/λ arcs, there is an arc that will not be used in the maximum capacity and so we can use it to send the extra unit. Applying this method iteratively from v i pi to v i 1 , we arrive at v i 1 with 2 units of flow on the flows x i 1 , . . . x i mi and we can send the extra unit of each flow to t because m i ≤ e i . ♦

For each i ∈ [ ], we compute the flows x i 1 , x i 2 , . . . , x i k as in the Claim 1. Observe that k is the number of flows that reach t. If k = k, then we can rename these k flows in such a way that each x j = i=1 x i j is an s-branching flow on N . Finally, if k > k, we take a flow that reaches t and we modify it so that it doesn't reach t anymore, and we repeat this process until there are only k flows that reach t.

It is worth to notice that the above proofs for multi-branchings and multi-spindles together with Proposition 1, besides giving a complete characterization of the digraphs in these classes having k arc-disjoint characterization of digraphs containing 2 arc-disjoint s-branchings also characterizes the existence of 2 arc-disjoint s-branching flows. Theorem 9. Let N = (D, u) be a (2, n -2, s)-sufficient network with u ≡ n -2. Then N admits 2 arc-disjoint s-branching flows.

Proof: Since N = (D, u) is a (2, n -2, s)-sufficient network, then for every X ⊂ V (D) \ {s} we have d - D (X) ≥ 2,
and for X = V (D) \ {s} we have d - D (X) ≥ 4. By Edmonds' Theorem, D has two arc-disjoint s-branchings. Let us call these s-branchings B b and B g and let us colour blue the arcs used by B b , green the arcs used by B g , and black the arcs of D not used by any of those branchings (observe that every vertex in V (D) \ {s} is the head of exactly one blue and exactly one green arc). The idea is to construct the desired s-branching flows using the arcs of B b and B g . This will be possible unless we are forced to send n -1 units of flow through an arc, which can only happen from an arc that leaves s. In this particular case, we show how to modify the branchings to avoid the problem. Thus we can assume w.l.o.g. that every out-neighbour of s in D is either blue or green and, from such arcs, exactly one is blue (sr b ) and the remaining are green. Notice that, since d - D (V (D) \ {s}) ≥ 4, there must be at least three green arcs from s to D \ {s}.

Since B g is a s-branching, r b appears in only one B g i , and let us consider a r g j for which B g j = B g i . Except for sr g j , there are no green arcs entering or leaving B g j . Then, let E be the set of blue arcs entering V (B g j ) together with all blue arcs between vertices in V (B g j ). We now recolour blue the arcs in A(B g j ) ∪ sr g j and yellow the arcs in E. After this recolouring, a vertex w = s is the head of exactly one blue arc and one yellow arc if it is in V (B g j ), otherwise it is still the head of exactly one blue and one green arc. This means that the vertices of V (D) along with the blue arcs will form a s-branching B b . In particular, there are two blue arcs leaving s in B b and we can construct the branching flow f b as before.

We now recolour the arcs of E green. Again, we have the guarantee that every vertex in B g j has exactly one green arc arriving at it (the former yellow arcs), and, since the green arcs outside A(B g j ) ∪ sr g j remain unaltered, the new set of all green arcs also form a s-branching B g . Once more, we have at least two arcs leaving s in B g , and we can construct f g as before.

We remark that, by a result of [START_REF] Bang-Jensen | The complexity of finding arc-disjoint branching flows[END_REF], deciding if a network with u ≡ n -2 admits arc-disjoint flows can be done in polynomial time. Since Theorem 9 completes the proof that a network is (2, n -2, s)-sufficient if and only if it admits 2 arc-disjoint s-branching flows (together with Proposition 1), we get that it can be decided in polynomial time whether a digraph is (2, n -2, s)-sufficient. (ii) X ∩ V (P 0 ) = ∅. Then |X| ≤ λ|I| + λ = λ(|I| + 1). Take the smallest j such that v 0 j ∈ X. We analyze two possibilities:

v 0 1 v 0 2 v 0 λ k . . . k . . . ... v 1 1 v 1 2 v 1 λ-a 1 k . . . k . . . ... v 2 1 v 2 2 v 2 λ-a 2 k . . . k . . . ... v 3k 1 v 3k 2 v 3k λ-
(ii.1) j > 1. Then there are k arcs v 0 j-1 v 0 j that enter X, that is, d -(X) ≥ k|I| + k = k(|I| + 1) ≥ k |X|/λ since |I| is a positive integer and |X| ≤ λ(|I| + 1), a contradiction. (ii.2) j = 1. Therefore v 0 1 ∈ X and d -(X) ≥ k|I|.
Again, we consider some cases: (ii.2.1) If there are at least k different values of i for which v i λ-ai ∈ X, then such vertices contribute with k to the in-degree of X, and again we have d -(X) ≥ k|I| + k. (ii.2.2) If there is only 1 ≤ l < k different values of i for which v i λ-ai ∈ X, then, in order to complete the argument, we need to estimate more precisely the size of X. Recall that λ/4 < a i < λ/2. So, |X| ≤ λ|I| -λ|I| 4 + λ = λ( 3|I| 4 + 1). Observe that the amount of arcs entering X is k|I| + l = 3k|I| 4 + k|I| 4 + l. Since, in this case, |I| > 2k, we have that k|I| 4 ≥ k 2 2 > k if k > 2, which we can consider true by the definition of the 3-PARTITION problem (k < 3 would be directly a negative instance). Then, As we got a contradiction on each case, it follows that D is (k, λ, s)-sufficient.

d -(X) ≥ 3k|I| 4 + k = k(λ( 3|I| 4 +
Now we assume that there exists k subsets S 1 , S 2 , . . . , S k so that aj ∈Si a j = λ, 1 ≤ i ≤ k. In order to construct the arc-disjoint s-branching flows x 1 , x 2 , . . . , x k in N , we establish that each of the k copies of a multiple arc belongs to a different flow.

For every 1 ≤ i ≤ k, we construct x i in the following way: If a j / ∈ S i , the arc sv j 1 of x i will carry λ -a j units of flow. If a j ∈ S i , the arc sv j 1 of x i will carry λ units of flow. Since aj ∈Si a j = λ, the three arcs v j λ-aj for a j ∈ S i will send the amount of flow needed to complete the branching flow in P 0 . Finally, we assume that there exist k arc-disjoint s-branching flows x 1 , x 2 , . . . , x k in N . We first claim that x r (v i λ-ai v 0 1 ) ≤ a i , for all r ∈ [k], i ∈ [q]. Since x 1 , x 2 , . . . , x k are arc-disjoint, there is only one 14 Cláudio Carvalho et. al flow x t which is positive in v i λ-ai . If x t (v i λ-ai v 0 1 ) > a i , then, as |V (P i )| = λ -a i , v i 1 must receive more than λ units of flow in x t , that is, x t uses at least two copies of the arc sv i 1 . This is a contradiction because there are only k copies of sv i 1 and each flow must use exactly one copy. Thus, the claim follows. Each x r must reach v 0 1 with λ units of flow. Since λ/4 < a i < λ/2, each x r should use three arcs of the type v j λ-aj v 0 1 , and the correspondent a j forms a S r . Then S 1 , S 2 , . . . , S k is an yes instance of the 3-PARTITION problem.

Observe that, by the proof of Theorem 11, the networks constructed from negative instances of the 3-PARTITION problem are also examples that (k, λ, s)-sufficiency does not guarantee the existence of k arc-disjoint s-branching flows.

Concluding remarks

In this work, we studied the characterization of networks admitting k arc-disjoint s-branching flows. We showed that, in some cases (Theorems 4 and 5), an "Edmonds like" condition, which we call (k, λ, s)sufficiency, is enough to guarantee the existence of the k arc-disjoint s-branching flows but, in other cases, a stronger statement is needed (Section 2). This proves that (k, λ, s)-sufficiency in general is not enough to guarantee the existence of the desired s-branching flows in networks, although the cases for which it does are still interesting because, among other reasons, they have been resulting in polynomial-time algorithms to find the flows. Some of the positive results we prove consider restrictions on the structure of the digraphs on which the networks are built: we show that the analyzed property guarantees the existence of the flows on multi-spindles and on multi-branchings. In other words, we prove that the flows always exist in (k, λ, s)-sufficient networks built on digraphs whose underlying simple graphs are trees or spindles.

Another direction of this research would be to work on the characterization through a stronger condition, as cited before. Some interesting complexity questions are still open, such as a possible dichotomy in DAG's between the easy and hard cases. In other words, it would be very interesting to know if there a class of digraphs H, all of which are DAGs, such that every (k, λ, s)-sufficient network constructed on a digraph D ∈ H contains k arc-disjoint s-branching flows, but that the same is not true for every D ∈ H.

Fig. 1 :

 1 Fig. 1: Example of a network on a (2, n -3, s)-sufficient digraph that does not contain 2 arc-disjoint s-branching flows. Here every arc has capacity n -3.

Theorem 2 .

 2 For every c ≥ 3, there exists a (2, n -c, s)-sufficient network N which does not admit 2 arc-disjoint s-branching flows.Proof: Let N be a network as in Figure1, considering that B has exactly c vertices and |A| = n -c -1, with each of the last c vertices of A connected to a different vertex of B. First, we show that N is (2, n -c, s)-sufficient. For any set X ⊆ V (D) \ {s}, let a = |X ∩ A| and b = |X ∩ B|. Thus, |X| = a + b.

Fig. 2 :

 2 Fig. 2: Counter-example for k = 2 and λ ≥ 2

  ) and 3(b) for an example of a multi-branching and an example of a multi-spindle, respectively.

Fig. 3 :

 3 Fig. 3: Examples of multi-branching (a) and multi-spindle (b)

Theorem 5 .

 5 If D is a (k, λ, s)-sufficient digraph in D , then the network N = (D, u) with u ≡ λ admits k arc-disjoint s-branching flows.

Let r b 1 ,

 1 . . . , r b be the out-neighbours of s in B b and let B b 1 , . . . , B b be the maximal sub-branchings of B b \ {s} with roots r b 1 , . . . r b , respectively. If > 1, then we can construct a branching flow f b from B b by sending |B b i | units of flow through sr b i , for 1 ≤ i ≤ , which is possible because u ≡ n -2. The same applies to B g and we will exchange b to g in the above notation when it concerns B g in the rest of the proof. If s has only one out-neighbour r b in B b , but there is a black arc sv, we can construct f b from B b ∪ sv. We have to consider two cases: if v = r b , let uv ∈ A(B b ) and let B b v be the maximal connected subgraph of B b \ {u} with root v. Then we send |B b v | units of flow through sv and |B b \ {s}| -|B b v | through sr b . Otherwise, v = r b and we have two copies of the arc sv. So we can send 1 unit of flow through one and n -2 through the other. In both cases, for the remaining blue arcs, we just need to adjust the proper amount of flow. The same applies to B g .

Fig. 4 :

 4 Fig. 4: The network N = (D, c) constructed from an instance of the 3-PARTITION problem (i) V (P 0 ) ∩ X = ∅. Then |X| ≤ λ|I| and |X|/λ ≤ |I|, so d - D (X) ≥ k|I| ≥ k |X|/λ , a contradiction to the choice of X.

  1)/λ), a contradiction. (ii.2.3) If all the last vertices are in X, then d -(X) ≥ d -(V -s), and we have another contradiction, since |X| < |V (D) -s|.

(i) The underlying graph of a digraph D is the undirected graph obtained by ignoring the orientation of the arcs of D.

FUNCAP Pronem 4543945/2016, CAPES/STIC-AmSud 88881.197438/2018-01 and PhD scholarship granted by CAPES. ‡ French Agence Nationale de la Recherche under contract ASSK ANR-18-CE40-0025-01. Work partially done at UFC(MDCC), with a PhD scholarship by FUNCAP. § FUNCAP 186-155.01.00/21 and 4543945/2016 (Pronem). ¶ French Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01. FUNCAP Pronem 4543945/2016, and CNPq project 304831/2017-4.

Cláudio Carvalho et. al branching flows, they lead to polynomial-time algorithms to find such flows, once testing the (k, λ, s)sufficiency for multi-branchings and multi-spindles can be done in polynomial time. The algorithms work for every value of λ, even those for which the problem of finding k arc-disjoint branching flows is known to be hard in general.

We now consider the cases of k or λ with value 1 and for that we need the three following results.

Theorem 6 (Max-flow min-cut). In any network N = (D, u) with source s and sink t, the value of a maximum flow is equal to the capacity of a minimum cut.

Theorem 7. [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF] Let k be an integer and N = (D, u) be a network with u ≡ 1 and a prescribed balance vector b such that b ≡ 0. There exist k arc-disjoint flows in N , all with balance vector b, if and only if N has a flow f with balance vector b f ≡ kb. Hence, one can decide the existence of these flows in polynomial time.

Lemma 2 (Adapted from [START_REF] Bang-Jensen | Digraphs: theory, algorithms and applications[END_REF]). Given a network N = (D, u) and a prescribed balance vector b. Let M = v:b(v)>0 b(v) and let N = (D , u ) be a network defined as follows:

Then, N admits a flow f with balance b if and only if N admits a (s , t )-flow f with value M .

. Then, we might assume that s ∈ S and we define

Case λ = 1. Since D is (k, 1, s)-sufficient, d - D (X) ≥ k|X| and resuming (4), we have u(S, S) ≥ k|X| + k(n -|X| -1) = k(n -1). Thus, u(S, S) = k(n -1) and, by the Lemma 2, N admits a flow with balance b f . The result follows from Theorem 7 which states that N admits k arc-disjoint s-branching flows if and only if it admits a single flow f with balance b f .

Case k = 1. Here, D is (1, λ, s)-sufficient, which means that d - D (X) ≥ (|X|/λ), and so λd - D (X) ≥ |X|. Replacing this in (4), we obtain u(S, S)

Similarly to the previous case, we conclude, by the Lemma 2, that N admits a flow f with balance b f . As k = 1, we have that f is a branching flow and the result follows.

We also show that networks on (2, n -2, s)-sufficient digraphs contain 2 arc-disjoint s-branching flows. This is a slightly improvement on the result by [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF] when k = 2, which states that Edmonds'

Cláudio Carvalho et. al

We end this section showing that, for particular choices of d - D (X) and λ, a simple stronger condition than the one presented in the statement of Proposition 1 guarantees the existence of k arc-disjoint sbranching flows in a given network. Theorem 10. Let N = (D, u) be a network with u ≡ λ and λ ≥ 2, and p be an integer such that pλ ≥ n -1. If d - D (X) ≥ pk for all X ⊆ V (D) \ {s} with X = ∅, then N admits k arc-disjoint s-branching flows.

Proof: By Theorem 1, there are pk arc-disjoint s-branchings B 1 , . . . , B pk in D.

Now, for every non-empty X ⊆ V (D) \ {s}, we conclude that d - Di (X) ≥ p since each B i with i ∈ [pk] must reach X at least once. Moreover, by our choice of p, we have that every N i is (1, λ, s)-sufficient. Thus, by Theorem 8, we have that each N i admits an s-branching flow x i . Finally, as every arc of D appears in at most one digraph D i , we conclude that the s-branching flows x 1 , . . . , x k are pairwise arcdisjoint. The result follows since each of these flows can be promptly used to construct an s-branching flow in N , by copying arcs and flow functions used by each flow x j with j ∈ [k].

Hardness of finding the flows in (k, λ, s)-sufficient networks

We showed in Sections 2 and 3 that there are networks N = (D, u), with D being (k, λ, s)-sufficient, which have k arc-disjoint s-branching flows and others that do not have such flows. We believe it is not always computationally easy to check the (k, λ, s)-sufficiency of a digraph, but, even if we know that D has such property, it is hard to decide if the desired flows exist, even if the network is constructed on a digraph formed by appending a path to the sink vertex of a multi-spindle. Theorem 11. Given two integers k and λ it is NP-complete to decide whether a (k, λ, s)-sufficient network N = (D, u) with u ≡ λ admits k arc-disjoint s-branching flows.

Proof: We are going to reduce the 3-PARTITION problem to our problem. Given a set of natural numbers S = {a 1 , a 2 , . . . , a 3k } and a positive integer λ such that λ/4 < a i < λ/2, for each a i ∈ S, and such that 3k i=1 a i = kλ, the 3-PARTITION problem consists in deciding the following: can S be partitioned in k subsets S 1 , S 2 , . . . , S k so that aj ∈Si a j = λ, 1 ≤ i ≤ k? Observe that each S i should be composed by exactly 3 elements of S.

From S, we construct a network N = (D, u) such that D is a (k, λ, s)-sufficient network that admits k arc-disjoint branching flows x 1 , x 2 , . . . , x k if and only if S is a yes instance of the 3-PARTITION problem.

We begin the construction by adding a vertex s, a multi-path P 0 = (v 0 1 , v 0 2 , . . . , v 0 λ ) and, for every i ∈ [3k], multi-paths P i = (v i 1 , v i 2 , . . . , v i λ-ai ), each one with k parallel arcs between consecutive vertices. Also, for every i ∈ [3k], we add one arc v i λ-ai v 0 1 and k parallel arcs sv i 1 . See Figure 4. Finally, we set u ≡ λ to conclude the construction.

First, let us check that D is (k, λ, s)-sufficient. By contradiction, assume that there exists a set X ⊆ V (D) -s such that d - D (X) < k |X|/λ . Note that X = V (D) -s since |V -s| = (2k + 1)λ and d - D (V -s) = k(3k). Recall that the in-degree of every vertex of P i is k and thus the in-degree of X is at least k. Therefore X cannot be entirely contained in a unique P i , i ∈ [3k], once, in this case, |X| ≤ λ and then |X|/λ = 1. Similarly, X cannot be entirely contained in P 0 , since there are 3k arcs arriving in v 0 1 . Now, let I = {i : 1 ≤ i ≤ 3k, V (P i ) ∩ X = ∅}. Observe that d - D (X) ≥ k|I|. We are going now to consider the following cases:


Sabine Kraushaar

Olivier Evrard

Tracing Events 2021-2023; Discussion and developments in sediment tracing

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Context

• Tracing or "fingerprinting" methods are used to identify sediment sources and quantify the dynamics of particle-bound contaminants.

• The use of these techniques is often associated with several methodological and statistical limitations.

• These are often reported, but rarely adressed in the framework of concerted actions. International Tracing Day (2022-2023) TRACING 2020 > 2021 School Sabine Kraushaar 1 , Olivier Evrard 2 and the TRACING Event organisers and participants 1 Institute of Geography and Regional Sciences, University of Vienna, Vienna, Austria (sabine.kraushaar@univie.ac.at) 2 Laboratoire des Sciences du Climat et de l'Environnement (LSCE), Université Paris-Saclay, France (olivier.evrard@cea.fr) Interested in participating ?

Upcoming actions

• 2022 and 2023, before the EGU, an International Study Day took place

• AIM: Practical plans to make progress regarding three main issues:

1. design of tomorrow's tracers, 2. optimized modelling methods, 3. organisation of an inter-comparison tracing exercise.

Use geomorphological information:

• scrutinize all the knowledge available on the catchment,

• obtain multiple lines of evidence regarding sediment contrib.

Improve scientific knowledge with local expertise:

• describe different levels of involvement of locals in research.

3. Use state-of-the-art sediment tracing protocols to conduct sampling:

• deal with particle size, examine data before modelling,

• account for the hydro-meteorological context.

Best practices in modelling:

• run multiple models and select appropriate tracers,

• report on model errors and uncertainty.

Share tracing data and samples:

• increase the visibility of the fingerprinting technique.

6. Formulation of hypotheses:

• improve the knowledge about erosion and sediment transport processes in a more unified way.

• Preparation of a data paper with a sufficient number of sediment tracing datasets in contrasted environmental contexts,

• Presentation of the approach and testing a common research hypothesis.

Supporting organisations

  Want to add to the current data compilation? Interested in taking part in the hypothesis testing exercice? Or the next International Tracing Day in 2024, just before the EGU? Please feel free to contact Sabine and Olivier! International Tracing Events 2021-2023 Discussion and developments in sediment tracing • 4-days seminar in Oct. 2021 • AIM: Concrete suggestions to improve the design and implementation of tracing methods.

⇒

  Need to compile international ensemble of data sets (and possibly samples) with the same format to test hypotheses. ⇒ Increase the visibility of our community and its ability to address the Subsoil erosion is the major process of sediment supply to river systems Suggested test hypothesis applicable in a large data set of various environmental conditions


Arthur Vervaet
email: arthur.vervaet@outscale.com

Mar Callau-Zori. Raja Chiky
email: raja.chiky@isep.fr

Mar Callau-Zori

Automatisation de la structuration des logs pour le Cloud Computing

Les registres de logs sont une composante fondamentale des systèmes informatiques modernes. Ils permettent aux équipes d'analyse et de surveillance de comprendre les comportements anormaux ou malveillants ayant pu survenir. Cependant, l'augmentation permanente du volume de logs générés par ces systèmes a rendu impossible l'inspection manuelle et pose un véritable défi d'automatisation du processus. Afin de traiter automatiquement ces données, plusieurs solutions de structuration des logs ont vu le jour. Dans cet article, nous analysons les capacités de deux d'entre elles à répondre aux enjeux du Cloud Computing en termes d'efficience et d'efficacité. Nos travaux se concentrent sur l'impact des paramètres et du prétraitement sur les performances de ces méthodes, deux étapes importantes, car nécessitant une intervention humaine incompatible avec l'automatisation du processus de structuration des logs.

Introduction

Les plateformes de Cloud Computing mettent à disposition de leurs clients différentes ressources informatiques à la demande. Cette externalisation rend les fournisseurs garants de la haute disponibilité et de la qualité de leurs services. La gestion d'un parc de ressources mutualisées en croissance constante demande de minimiser l'intervention humaine afin de suivre le changement d'échelle des infrastructures et d'éviter les erreurs. Pour atteindre cet objectif, on doit pouvoir se servir de toutes les informations à disposition afin de développer des outils autonomes servant à contrôler et assurer le respect de la qualité de service.

La journalisation des événements ou logs, consiste à enregistrer de manière détaillée des informations relatives à un programme pendant son exécution. Ces logs constituent une source d'information précieuse, utilisée pour retracer les différentes étapes d'un processus à la recherche de l'origine d'erreurs ou de pannes, mais également pour identifier des anomalies de performance ou analyser les statistiques d'utilisation [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF].

Malgré toutes les possibilités offertes par les logs et l'information qu'ils contiennent, les traiter efficacement est une tâche complexe. Les développeurs ayant très peu de contraintes dans l'écriture des macros destinées à produire les messages logs, ceux-ci suivent un format semi-structuré. Par exemple, le protocole RFC 5424 pour rsyslog (Network Working Group, 2009) fixe un format en trois parties : un en-tête (HEADER), une partie optionnelle pour des données structurées (STRUCTURED-DATA) et un message (MSG). À l'inverse du HEADER qui possède un format prédéfini contenant la priorité et l'origine du message, le champ MSG doit uniquement contenir un message libre fournissant des informations sur l'événement.

Du fait de la complexité croissante et du besoin de scalabilité des plateformes Cloud, la volumétrie des logs ne fait qu'augmenter, et ce de façon rapide. En 2013, Alibaba produisait environ 30 à 50 gigaoctets (environ 120 à 200 millions de lignes) par heure [START_REF] Mi | Toward fine-grained, unsupervised, scalable performance diagnosis for production cloud computing systems[END_REF]. [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF] évoquent un système de Huawei produisant plusieurs téraoctets de logs par jour en 2019. De notre côté, nous produisons actuellement chez 3DS OUTSCALE (fournisseur de Cloud français) une moyenne de 250 000 logs par seconde dans un de nos systèmes. Le traitement de cette volumétrie demande un système autonome nécessitant le moins d'intervention humaine possible. Afin de réagir le plus rapidement possible à une potentielle dégradation du service fourni, ce système doit pouvoir fonctionner en temps quasi réel.

L'importance de la structuration des logs a motivé la recherche et durant ces dernières années plusieurs comparatifs des algorithmes existants ont vu le jour [START_REF] He | An evaluation study on log parsing and its use in log mining[END_REF][START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF]. Ces études évaluent la précision et la robustesse de différentes solutions de structuration des logs sur des jeux de données provenant d'applications différentes. Les résultats de ces études illustrent l'utilisation possible de méthodes existantes pour le traitement des logsen temps réel. Cependant, à notre connaissance aucune étude ne pointe les limites restantes pour une automatisation complète du processus. En utilisant deux méthodes de traitement de logs, opérant en ligne et présentant de bons résultats, nous avons étudié deux points indispensables à leur automatisation : l'indépendance de ces méthodes au paramétrage et au prétraitement.

Nos contributions sont : une étude de l'impact du paramétrage sur la précision des méthodes et une étude de l'influence du prétraitement sur le temps de traitement et la précision. Ces travaux illustrent la faible dépendance d'une des méthodes étudiées au paramétrage avec cependant un impact modéré, mais potentiellement négatif du prétraitement sur sa précision. A contrario de la seconde méthode étudiée pour laquelle la précision et le temps de traitement dépendent fortement des étapes étudiées.

Dans ce qui suit, nous présentons l'état de l'art pour la structuration de logs(Sec. 2), dans la Sec. 3 nous présentons d'autres travaux comparatifs des algorithmes existants. La Sec. 4 présente notre étude des caractéristiques fondamentales pour un système autonome dans le Cloud : la précision et le temps de traitement en fonction du paramétrage et du prétraitement. Enfin, nous concluons le document dans la Sec. 5.

Structuration des logs

La structuration des logs se focalise sur la partie libre du message et cherche à identifier deux composantes : 1/ une composante fixe qui sert de patron 2/ une composante variable, contenant les spécificités du message. Dans le message " New process started: process x92 started on port 42", le patron identifié par l'expression régulière est "New process started: process . * started on port . * " ; le contenu spécifique est représenté par la liste : [x92, 42].

Trois qualités sont primordiales dans la structuration des logs : la précision, la robustesse et l'efficacité [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF]. La précision évalue la bonne détection des différentes parties d'un message. Dans un système où la volumétrie des logs à traiter est conséquente et peut évoluer rapidement, il est nécessaire de disposer de solutions robustes, à même de maintenir leurs performances dans un environnement changeant. Ces solutions doivent également être efficaces et capables de traiter les messages en temps quasi réel. Dans un cadre industriel, il est humainement coûteux et pas toujours possible d'obtenir un jeu de données labellisées pour paramétrer un système, d'où la nécessité de restreindre l'impact de cette étape sur les performances. Il est courant d'utiliser la connaissance d'un système pour commencer à structurer ses logs à l'aide d'expressions régulières servant à identifier des composantes variables. À l'aide d'expressions simples, on peut identifier le chiffre et l'adresse IP du message "Send 92 bytes to system x32 at 112.13.92.1" et ainsi obtenir un message prétraité : "Send * bytes to system x32 at * ", les * symbolisant l'emplacement d'une variable identifiée. L'inconvénient de ce prétraitement est qu'il demande une connaissance précise des données traitées et l'intervention d'un ou plusieurs experts pour définir les expressions régulières à employer. De plus, le prétraitement peut impacter négativement la performance (Section 4).

Les logs étant générés sous forme de flux, le meilleur moyen de les traiter est de suivre le même fonctionnement. Plusieurs log parsers présentés dans la littérature permettent cela. On retrouvera SHISO [START_REF] Mizutani | Incremental mining of system log format[END_REF] qui se base sur un arbre de structuration enrichi durant le fonctionnement, LenMa [START_REF] Shima | Length matters : Clustering system log messages using length of words[END_REF] qui utilise la séquence constituée par la longueur de chaque mot dans un log pour classifier une entrée, Spell [START_REF] Makanju | A lightweight algorithm for message type extraction in system application logs[END_REF] basé sur la recherche de la plus longue séquence commune pour rattacher un log à un patron déjà connu ou en découvrir un nouveau, et enfin Drain [START_REF] He | Drain : An online log parsing approach with fixed depth tree[END_REF] qui construit un arbre de partitionnement de profondeur fixe pour structurer les logs.

3 Travaux connexes [START_REF] He | An evaluation study on log parsing and its use in log mining[END_REF] présentent et comparent la précision et le temps de traitement de 4 méthodes de structuration sur 4 jeux de données issus d'applications différentes. Leurs travaux mettent en valeur l'importance du temps de traitement et de la distribution des calculs pour tenir la charge dans de gros systèmes industriels. De la même façon, les travaux de synthèse de Logpai [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF]

Évaluation

Nos travaux analysent l'impact du paramétrage et du prétraitement sur la précision et le temps de traitement des méthodes considérées. Cette section est consacrée à la présentation et à l'analyse des résultats obtenus.

Contexte expérimental. Comme discuté dans la Sec. 3, nous avons retenu Spell [START_REF] Du | Spell : Streaming parsing of system event logs[END_REF] et Drain [START_REF] He | Drain : An online log parsing approach with fixed depth tree[END_REF], solutions les plus prometteuses en vue de leur application dans un environnement Cloud. Deux métriques ont été choisies : la précision de structuration [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF] définie comme le rapport entre le nombre de logs dont le patron est correctement identifié et le nombre total de messages et le temps de calcul par log servant à représenter l'efficacité. Trois jeux de données libres, disponibles sur la plateforme LogHub1 ont été utilisés : OpenStack, Android et HDFS ; des échantillons labellisés de 2 000 lignes ont servi pour le calcul de la précision, les jeux de données complets ont eux été utilisés pour l'évaluation du temps de calcul. Nos expériences ont été réalisées sur une machine virtuelle Cloud de type CentOS Linux 7.8.2003 avec 62 GB de RAM.

Impact des paramètres sur la précision

Les paramètres sont des variables fixées lors de la configuration d'un système. Dans cette section, nous présentons une étude de l'influence de ces paramètres sur la précision de Spell et Drain afin de savoir si des valeurs génériques sont envisageables.

TAB. 3 -Expressions régulières utilisées dans le prétraitement

Spell n'utilise qu'un seul paramètre servant de seuil pour déterminer si un log appartient à un patron déjà connu, τ ∈ [0, 1], qui est le rapport entre la plus grande séquence commune et la longueur du log. De son côté, Drain possède deux paramètres : une profondeur de l'arbre de recherche depth et un seuil ST ∈ [0, 1] qui sert à déterminer si un log appartient à un groupe existant.

La Figure 1 présente l'évolution de la précision en fonction des valeurs des paramètres. La valeur de τ maximisant la précision de Spell diffère pour chaque jeu de données : 0,8 pour OpenStack, 0,85 pour Android et 0,5 pour HDFS. Le jeu de données le plus touché par le choix de τ est HDFS : la moitié des valeurs de τ considérées donnent une précision inférieure à 0,7, pouvant même faire tomber la précision à 0. Dans les deux autres jeux de données, le choix de τ peux faire gagner jusqu'à 15 % de précision pour OpenStack et 20 % pour Android. Drain a un comportement inégal pour les différents jeux de données. Bien que des valeurs élevées de ST (>0,7) ne donnent pas de bons résultats, la valeur de depth est importante pour obtenir des résultats précis pour OpenStack et Android. De plus, dans le cas d'Android, la précision maximale obtenue est de 0,75 alors que 0,9 est atteint dans les deux autres jeux. Pour les jeux de données concernés, Drain atteint la plus haute précision avec un ST compris en 0,2 et 0,5 ; depth en revanche est plus versatile, sa valeur optimale étant de 5 pour Android, 6 pour HDFS et 7 pour OpenStack. On peut conclure que la précision des deux solutions est influencée par les choix de paramètres.

Impact du prétraitement sur la précision

L'étape de prétraitement permet d'identifier des variables avant de commencer le processus de structuration d'un log. Nous avons sélectionné un ensemble d'expressions régulières (Tab. 3) identifiant des blocs bien connus dans chaque jeu de données, tels que les chiffres, les adresses IP ou les mots commençant par "blk_-" pour HDFS.

La Table 4 présente les résultats obtenus sur les échantillons de 2 000 lignes. Chaque méthode a tourné avec et sans prétraitement, nous avons calculé la précision, mais également le nombre de patrons afin de détecter une éventuelle surclassification des logs. Les paramètres utilisés sont ceux pour lesquels chaque méthode présente la plus haute précision avec prétraitement.

Spell arrive à multiplier par 1,5 sa précision avec l'utilisation du prétraitement, et même par 3,6 dans le cas de HDFS. Même constat pour les patrons : Spell bénéficie d'une influence Le prétraitement a donc un effet, mais pas toujours positif sur la précision. Cette étape est de plus coûteuse car exigeant de déterminer à l'avance les expressions régulières.

Impact sur le temps de calcul

Notre dernière évaluation porte sur le temps du traitement : celui-ci doit rester le plus bas possible pour espérer des résultats en temps réel. Nous avons dans un premier temps essayé de faire tourner Spell et Drain sans prétraitement mais le temps d'exécution de Spell était trop long. En effet, au bout de trois heures, Spell n'avait pas terminé les calculs et ce pour les trois jeux de données contre quelques dizaines de minutes avec prétraitement. Les valeurs présentées dans cette section concernent donc les résultats avec étape de prétraitement.

Les résultats présentés dans la Figure 2 montrent la distribution du temps de traitement sur les différents jeux de données. Le temps moyen de traitement de Drain reste dans un ordre de 10**2 ns sur chaque jeu de données et est toujours inférieur à celui de Spell. Il est également important de noter qu'il existe un nombre conséquent de logspour lesquels le temps de traitement peut être jusqu'à 500 fois supérieur à la moyenne. Il est important de noter ces temps divergents car ils sont susceptibles de créer des décalages par rapport au temps réel dans un environnement de production.

Conclusion et travaux futurs

L'analyse des fichiers de logs est primordiale pour la maintenance des systèmes informatiques et l'automatisation de celle-ci passe par une étape de structuration visant à exploiter l'information contenue dans les messages. Dans cet article, nous nous sommes intéressés à la robustesse et l'efficience de deux méthodes issues de la littérature récente. Ces deux aspects sont cruciaux dans un environnement Cloud où l'interaction humaine doit être minimale pour

  FIG. 1 -Précision en fonction des paramètres

  FIG. 2 -Temps de traitement total en fonction du nombre de logs déjà structurés

  Online log parsers présentés dans[START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF].

	Log parser	Année	Technique	Efficacité Couverture Pré-traitement
	SHISO	2013	Clustering	High	oui	non
	LenMa	2016	Clustering	Medium	oui	non
	Spell	2016	Longest common subsequence	High	oui	non
	Drain	2017	Parsing tree	High	oui	oui
		TAB. 1 -

  évaluent la précision, la robustesse et l'efficacité de 13 méthodes sur 16 jeux de données. La Table1résume les caractéristiques des méthodes analysées adaptées au traitement en flux des logs. Les solutions les plus prometteuses en termes d'efficacité sont Drain, Spell et SHISO, Drain étant présenté comme la solution la plus performante selon ces mêmes critères. L'article met en valeur la combinaison des résultats sur 16 jeux de données et l'impact fort du système d'information sur la précision des solutions.Nous avons choisi de concentrer nos expériences sur les deux méthodes présentant la meilleure précision dans les études précédentes : Spell et Drain. Dans le cadre de notre étude, Caractéristiques de certains jeux de données présentés dans[START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF].nous avons ciblé et repris des jeux de données proches de l'environnement d'un fournisseur de Cloud (Tab. 2), les méthodes variant en fonction du système d'information dont provient chaque jeu de données." OpenStack est une solution Cloud permettant un déploiement de plateformes IaaS ; le volume du jeu de données reste cependant trop faible pour l'assimiler à un acteur industriel. Nous avons retenu Android pour ses nombreux patrons différents et ses logs de type système d'exploitation (allocation de ressources, gestion des processus et du réseau, etc.). Pour finir, nous avons décidé de considérer HDFS, celui-ci étant largement utilisé dans la littérature malgré son aspect peu complexe et son faible nombre de patrons et de parties variables. Les travaux présentés dans cette section forment une base solide pour comparer di-

	Jeu de données	Taille	#Messages	#Patrons #Mots uniques
	OpenStack	60,01 MB	207,820	51	942
	Android	3,38 GB	30,348,042	76,923	3599
	HDFS	1,47 GB	11,175,629	30	1445
	TAB. 2 -

verses méthodes existantes dans de nombreux environnements. Toutefois, ils ne contiennent pas de données concrètes sur l'impact du paramétrage et du prétraitement sur la précision de l'analyse et le temps de calcul nécessaire pour traiter des jeux de données comme HDFS et Android.

  Précision en fonction du prétraitement positive en se rapprochant du nombre réel. Pour Drain, les résultats diffèrent selon le jeu de données, tandis que pour Android, nous notons une amélioration une amélioration similaire à celle de Spell avec le prétraitement. Pour OpenStack, la précision et le nombre de patrons empirent avec les mêmes expressions régulières grâce auxquelles on a constaté des améliorations dans le cas de Spell. Cette baisse de précision est liée à des mots de la forme 54b44eb-2d1a-4aa2-ba6b-074d35f8f12c présents dans 3 patrons. Sans prétraitement, celui-ci altère un niveau de l'arbre de partitionnement. En revanche, avec prétraitement ce mot est découpé en plusieurs parties : *b*eb-*d*a-*aa*-ba*b-*d*f*f*c et altère plusieurs niveaux de l'arbre , faisant ainsi tomber à 0 la précision de Drain pour tout log contenant ce type de mot. Spell n'est pas affecté car sa précision sur les patrons contenant ce mot est déjà nulle.

	Jeu de	Spell (sans)	Spell (avec)	Drain (sans)	Drain (avec)
	données	prec. nb. patrons	prec.	nb. patrons	prec. nb. patrons	prec.	nb. patrons
	Android	0.60	425	0.91(x1.5) 180(x0.42)	0.67	217	0.91(x1.4) 171(x0.79)
	HDFS	0.28	684	1.00(x3.6) 14(x0.02)	1.00	17	1.00(x1)	16(x0.94)
	O.Stack	0.23	692	0.77(x3.3) 451(x0.65)	0.84	75	0.73(x0.8) 299(x3.99)
			TAB. 4 -

https ://github.com/logpai/loghub

Summary

Logs are a fundamental component of modern computer systems. They enable the analysis and monitoring teams to understand any abnormal or malicious behavior that may have occurred. The continuous increase in the volume of logs generated by these systems made it unsuitable for manual inspection and represents a real challenge with regard to process automation. In order to process these data, several log-structuring solutions have been developed.

In this article, we analyze the capabilities of two solutions in order to meet the challenges of Cloud Computing in terms of efficiency and effectiveness. Our work focuses on the impact of parameterization and preprocessing on the performance of these methods-two important steps as they require human intervention, which is incompatible with with the automation of the log-structuring process.