Ronan Bocquillon
email: ronan.bocquillon@univ-tours.fr

Antoine Jouglet
email: antoine.jouglet@hds.utc.fr

Robust routing in deterministic delay-tolerant networks

Keywords: combinatorial optimization, robust optimization, constraint programming, delayand disruption-tolerant networks, store-carry-and-forward routing, systems of systems

A system of systems is a set of heterogeneous independent systems that share data in pursuit of a common goal. These systems form a delay-/disruption-tolerant network (DTN), where routing is based on the store-carry-and-forward paradigm. Systems can communicate whenever they are close enough to each other, in what are called contacts. We assume that the movements of these systems may be predicted in advance and we consider that a sequence of contacts is given at the outset. During a contact, a given emitting system can transfer to a given receiving system a fixed amount of data (termed datum unit) that it has in its possession. The dissemination problem is to find a transfer plan such that all the data can be transferred from a given subset of source systems to a given subset of recipient systems. In this paper we study the problem where communications may fail. We propose an algorithm for finding a robust transfer plan that minimizes the dissemination length.

Introduction

Mo Jamshidi has defined systems of systems as large-scale integrated systems that are heterogeneous, independently operable on their own, and networked together for a common goal [START_REF] Jamshidi | System of Systems Engineering: Principles and Applications[END_REF]. More precisely, in this paper, we consider a set of mobile systems which collaborate and share data to achieve a common objective. Due to their mobility, systems of systems may be sparse and lack continuous connectivity. They form a delay-/disruption-tolerant network (DTN) [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF].

Systems can only communicate when they are close enough to each other. Such an opportunity is termed a contact. Messages are then transmitted from one system to another -one contact after another -and stored throughout the network in the hope that each message will reach its destinations. This is called store-carry-and-forward routing.

To minimize latency or to maximize the chances of a message being successfully transmitted to its destinations, one commonly used solution, termed epidemic routing [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF], is to replicate messages and to spread many copies out over the network. Of course, this approach is not suitable where systems have limited memory capacity or where the bandwidth of links is low.

When systems produce contents that exceed the capacity of links, they must segment messages in order to transmit fragments (also termed datum units) separately. This raises the problem of which datum units to send during each contact (whenever systems meet). Belblidia et al. [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF] proposed, for example, a popularity-based decentralized heuristic which tends to homogenize the dissemination of each datum unit in the network.

This problem has exercised an increasing number of researchers over the last decade. Some [START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF][START_REF] Burns | MV routing and capacity building in disruption tolerant networks[END_REF][START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF] have proposed stochastic methods that estimate different probabilistic metrics to, in fine, decide which data are transmitted. Others [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF][START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF][START_REF] Jain | Routing in a delay tolerant network[END_REF][START_REF] Merugu | Routing in Space and Time in Networks with Predictable Mobility[END_REF] have considered deterministic time-evolving networks and proposed algorithms that optimize a given criterion (such as delay or robustness). These approaches consider that the sequence of contacts is given at the outset, and therefore focus on applications where it is possible to make realistic predictions on systems' movements. Such applications include satellite networks (where the trajectory of all systems depends on straightforward physics) and public transportation systems. For example, Jain et al. [START_REF] Jain | Routing in a delay tolerant network[END_REF] built an instance with 20 buses, equipped with wireless communication devices, making scheduled trips inside San Francisco.

Real-world applications include projects such as Bluespots [START_REF] Lebrun | Bluetooth content distribution stations on public transit[END_REF] (where a small computer on a bus serves as a bluetooth content distribution station in a university public transit scenario), the Disaster Monitoring Constellation [START_REF] Wood | Use of the Delay-Tolerant Networking Bundle Protocol from Space[END_REF] (a multi-satellite Earth-imaging low-Earth-orbit sensor network where captured image swaths are stored onboard each satellite, and later downloaded from the satellite payloads to a ground station) and DakNet. The latter is a (very) low cost storecarry-and-forward wireless ad-hoc network for rural connectivity. It uses public buses (or other physical transports) to carry mobile access points between village kiosks and a hub with Internet access (a town). Data automatically uploads and downloads when the bus is in range of a kiosk or the hub. It has already been implemented in India and northern Cambodia [START_REF] Pentland | DakNet: rethinking connectivity in developing nations[END_REF]. Of course one can easily imagine that buses collaborate to spread the data more efficiently.

So-called deterministic delay-and disruption-tolerant networks are at the heart of the present paper. We examine the problem, commonly termed the dissemination problem, of making use of knowledge about systems' movements when information needs to be routed from sources to destinations within a given time horizon. The fundamental question is which elements of the information should be transferred from which system to which system when contacts occur. A solution to this problem is termed a transfer plan.

We have previously addressed the case where transfers cannot fail [START_REF] Bocquillon | A constraint-programming-based approach to solve the data dissemination problem[END_REF][START_REF] Bocquillon | Modeling elements and solving techniques for the data dissemination problem[END_REF][START_REF] Bocquillon | The data transfer problem in a system of systems[END_REF]. We now propose to tackle a variant where failures are possible. We wish to find transfer plans guaranteeing that all datum units are correctly delivered to all recipient systems if no more than Γ ∈ N transmissions fail, regardless of those that actually fail (in accordance with the well-known approach proposed by Bertsimas and Sim [START_REF] Bertsimas | The Price of Robustness[END_REF]). By "failure" we of course mean anything that prevents a transfer terminating successfully (battery depletions, link problems, ...). In this way, we hope to cover a wider range of applications.

The rest of the paper is organized as follows. The robust dissemination problem is defined in Section 2. In Section 3 we describe an enumeration algorithm for finding all robust solutions. This algorithm is integrated into a constraint programming formulation in Section 4, and finally assessed in Section 5.

The robust dissemination problem

In this section the robust dissemination problem is formally defined. First we state the problem, then we discuss a well-known graph-based model to tackle it.

The robust dissemination problem

Let us now formally define the robust dissemination problem. We first consider a set N = {1, 2, . . . , n} of n interacting mobile systems, termed the nodes, and one datum D = {1, 2, . . . , u} of u datum units. Each datum unit (also termed unit) is a unitary and indivisible fragment of data. At the outset, each node i ∈ N possesses a subset O i ⊆ D of units. For distinct nodes i, j the sets O i , O j do not have to be disjoint. Subset R ⊆ N defines the nodes wishing to obtain the datum D (i.e. all the units) inside the given time horizon. For the sake of clarity, the term source nodes (or sources) will refer to the nodes i ∈ N | O i ∅. The nodes in R will be called the recipient nodes (or recipients).

To ensure the dissemination of datum D, nodes may exchange datum units whenever they are close enough to communicate. Such an opportunity is termed a contact. We assume that the trajectory of each node is deterministic and consequently that contacts are perfectly predictable. We actually consider that a sequence of contacts σ = (σ 1 , σ 2 , . . . , σ m ) of m ordered pairs of N 2 is given. During contact (s, r) ∈ σ, the sending node s can send to the receiving node r at most one unit that it already possesses (either from the outset or as a result of previous contacts). After this contact, if the transmission has been successful, node r also possesses a copy of datum unit k. Here we assume that all buffers are infinite, so a node can potentially possesses a copy of all the datum units. Below, nodes s c and r c will denote the sender and the receiver in contact σ c ∈ σ, i.e. σ c = (s c , r c ).

A transfer plan is a function φ : {1, 2, . . . , m} → {∅, {1}, {2}, . . . , {u}} where φ(c) designates the datum unit sent by node s c during contact σ c . Note that φ(c) = ∅ if nothing is transferred during contact σ c . Such a transfer is said to be null. Thus, for a given transfer plan φ and a given set of failures, we can compute the subset of datum units possessed by any node at any time. Formally, given an indicator function S : {1, 2, . . . , m} → {0, 1} such that S(c) = 0 stands for a success and S(c) = 1 for a failure of transmission φ(c), we define the subset O t i (S, φ) ⊆ D of units possessed by node i ∈ N at time t ∈ {0, 1, . . . , m} as follows:

(1) ∀i ∈ N, O 0 i = O i , (2) ∀c ∈ {1, 2, ..., m} | S(c) = 1, ∀i ∈ N, O c i = O c-1 i , (3) ∀c ∈ {1, 2, ..., m} | S(c) = 0, O c r c = O c-1 r c ∪ [ φ(c) ∩ O c-1 s c ], (4) ∀c ∈ {1, 2, ..., m} | S(c) = 0, ∀i ∈ N\{r c }, O c i = O c-1 i .
The transfer plan φ is valid if all intended transmissions are possible in the most favorable case where no failure occurs. If we denote by S * the constant function S * (c) = 0, then φ is valid if and only if

∀σ c ∈ σ, φ(c) ∈ {∅} ∪ {{k} | k ∈ O c-1
s c (S * , φ)}. A valid transfer plan φ has a delivery length λ Γ i (φ), for each node i ∈ N, which corresponds to the smallest time index t at which it can be guaranteed that i possesses all the datum units if at most Γ ∈ N transmissions fail (regardless of which Γ transmissions fail), i.e.

λ Γ i (φ) = min { t ∈ {0,
Γ i (φ) = ∞. The dissemination length λ Γ (φ) = max i∈R {λ Γ i (φ)
} corresponds to the time index at which we can guarantee that all the recipient nodes possess all the datum units if at most Γ transmissions fail.

Given a set of nodes N = {1, 2, . . . , n}, a set of datum units D = {1, 2, . . . , u}, the subset O i ⊆ D of datum units possessed by each node i ∈ N at the outset, a subset R ⊆ N of recipient nodes, a sequence of contacts σ = (σ 1 , σ 2 , . . . , σ m ) such that ∀c ∈ {1, 2, . . . , m}, σ c ∈ N 2 and a limit Γ ∈ N on the number of failures, the robust dissemination problem is to find a valid transfer plan φ minimizing the dissemination length λ Γ (φ).

Remark 2.1. Note here that many other objectives could have been studied, e.g. we could have minimized the number of contacts that are really tapped to optimize the energy consumption of the network. We leave this for future works. [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF][START_REF] Bertsimas | The Price of Robustness[END_REF], [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF][START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF], . . . , [START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF][START_REF] Bertsimas | The Price of Robustness[END_REF] Γ is a key parameter that characterizes the minimum level of robustness that any solution must guarantee. A transfer plan φ is Γ-robust if and only if λ Γ (φ) ∞. Γ-robust solutions are the only admissible solutions for the robust dissemination problem, which means that an instance may be feasible with a given value of Γ, but infeasible with a greater value of that parameter. However, Γ-robust transfer plans are always p-robust for all 0 ≤ p ≤ Γ.

         N = R = {1, 2, 3, 4}; D = {1, 2} O 1 = {1, 2}; O 2 = {1}; O 3 = O 4 = ∅ σ = ((1, 3),
) (b) a solution of 3 arc-disjoint branchings          φ(3) = φ(7) = {1} φ(1) = φ(2) = φ(5) = {2} φ(4) = φ(6) = ∅ (c) evolving graph [12]
The robust dissemination problem is NP-Hard in the strong sense, since the dissemination problem (a strongly NP-Hard problem [START_REF] Bocquillon | The data transfer problem in a system of systems[END_REF]) is a special case of the robust dissemination problem where Γ = 0.

Evolving graphs

An instance of the robust dissemination problem is described by a multigraph whose vertices represent the set of nodes N, and whose arcs represent the sequence of contacts σ. Each arc is labeled with the position in σ of the contact to which it corresponds. Such a graph is commonly called an evolving graph [START_REF] Ferreira | Building a reference combinatorial model for MANETs[END_REF]. To appropriately take account of time constraints, the concept of path is replaced by the concept of journey, which is a sequence of arcs having increasing labels (a sequence of arcs that respect the order imposed by σ).

In Figure 1, [σ 1 = (1, 4), σ 2 = (4, 3)] is a journey (since 1 ≤ 2). This represents the fact that node 4 can forward the unit it receives from node 1 at time 1 to node 3 at time 2. Nevertheless, [σ 6 = (3, 2), σ 4 = (2, 4)] is not a journey (because 6 > 4). More generally, given a datum unit k ∈ D, a journey [(i, u), . . . , (v, j)] between a source node i ∈ N | k ∈ O i and a recipient node j ∈ R represents a store-carry-and-forward routing to transfer unit k from i to j.

Thus, a store-carry-and-forward routing to transfer a given unit k ∈ D to all the recipient nodes R is defined in the evolving graph by a set of arc-disjoint branchings that are rooted on the source nodes of unit k, and such that all the recipient nodes are covered. It is recalled that a branching is an evolving graph in which, for a vertex u called the root and any other vertex v, there is exactly one journey from u to v.

For example, in Figure 1, the double arcs define a branching to disseminate datum unit 2 from the unique source node 1 to all the other nodes. Similarly, the bold arcs define a set of branchings to disseminate datum unit 1 from the two source nodes 1 and 2 to all the other nodes. Note that, in the following, such a set of branchings is simply termed a covering branching, since it can be seen as a single branching if we imagine a virtual root node that transfers datum unit k to the source nodes (1 and 2) at time 0.

Solving the non-robust dissemination problem (Γ = 0) is therefore equivalent to finding u arc-disjoint covering branchings of this type (one per datum unit) [START_REF] Bocquillon | The data transfer problem in a system of systems[END_REF].

An intuitive extension to the robust case consists in searching for exactly Γ + 1 arc-disjoint covering branchings per datum unit. The resulting transfer plan (built from the (Γ + 1) × u covering branchings) is Γ-robust. It defines how Γ+1 copies of each datum unit can be transferred (along independent and contact-disjoint journeys) to the recipient nodes. Γ failures will never be enough to prevent any given node receiving a given datum unit. However, it is worth noting that this approach is over-protective. The existence of (Γ + 1) × u covering branchings is a sufficient but not a necessary condition for a Γ-robust solution to exist.

This last point is very important and actually justifies this study. Since solving the robust case is not equivalent to solving the initial problem simply by considering Γ + 1 times more datum units, we cannot directly use the algorithms that we proposed for the non-robust case.

Proposition 2.1. The existence of at least (Γ+1)×u mutually arc-disjoint covering branchings in the evolving graph (Γ + 1 covering branchings per datum unit) is a sufficient, but not necessary, condition for a Γ-robust transfer plan to exist.

Proof. The condition is sufficient, because Γ failures are not enough to invalidate Γ + 1 mutually arc-disjoint covering branchings.

To prove this is not necessary, we consider the following instance: We assume that R = N = {t, a, . . . , f } (all nodes are recipients). The valid transfer plan φ such that ∀c ∈ {1, 2, . . . , 12}, φ(c) = {1} is 1-robust since no single failure can prevent the correct delivery of unit 1. Yet, we can show that there do not exist two arc-disjoint covering branchings rooted at node t (the source) in this evolving graph. To demonstrate this, let us first suppose that there are two arc-disjoint covering branchings B 1 and B 2 rooted at t. Each covering branching has exactly 6 arcs. Thus,

{B 1 , B 2 } is necessarily a partition of the set A = {a 1 , a 2 , . . . ,

Robust optimization

In this section we propose a branching algorithm for enumerating all valid Γ-robust transfer plans. The procedure is based on a necessary and sufficient condition of robustness that we will proceed to discuss. We also propose a polynomial-time algorithm to check that a given solution is Γ-robust. This branching algorithm will be incorporated into the branch-and-bound procedure described in Section 4.

Necessary and sufficient condition for a transfer plan to be Γ-robust

In the worst case, all the failures prevent the same node r ∈ R receiving the same unit k ∈ D (the failures invalidate all the journeys going from a source of k to node r in the evolving graph). Thus, if we wish to prove that a given valid transfer plan φ is Γ-robust, it will be enough to show that for all datum units k ∈ D and all recipient nodes r ∈ R, the number of contacts that have to fail to prevent r from receiving k is strictly greater than Γ. With this aim in view, for each unit k ∈ D and each node r ∈ R, we consider the flow network G(φ, k, r) = (X, U) built as follows.

1. First, we add a source vertex src ∈ X and a sink node snk ∈ X. 2. For each node i ∈ N, we add

µ i + 1 nodes {i 0 , i 1 , . . . , i µ i } ⊆ X, where µ i = |{ σ c ∈ σ | r c = i }|
is the number of contacts whose receiver is i. 3. We add one arc (src, i 0 ) ∈ U for each source node i ∈ N | k ∈ O i , and one arc (r µ r , snk) ∈ U.

These arcs all have an infinite capacity. 4. For each node i ∈ N, we add arcs {(i 0 , i 1 ), (i 1 , i 2 ), . . . , (i µ i -1 , i µ i )} with infinite capacities. 5. For each contact σ c = (i, j) ∈ σ such that φ(c) = {k}, we add an arc (i x , j y ) ∈ U of capacity 1.

x denotes the number of contacts occurring before σ c and whose receiver is i. y is set so that σ c is the y th contact whose receiver is j.

The units of flow traversing a vertex i x ∈ X (cf. item 2) correspond to the copies of datum unit k that are transferred to node i ∈ N during the first x contacts in σ of which it is the receiver. These units of flow come from vertex i z-1 ∈ X through an arc of infinite capacity (this represents the fact that nodes can stores datum units over time, cf. item 4) and/or from another vertex j y ∈ X through an arc of capacity 1 (this corresponds to a transfer during a contact, cf. item 5). The arcs discussed in item 3 just ensure that the sources of datum unit k can store as many copies of k as needed. Note finally that vertex snk ∈ X collects the units of flow corresponding to what node r receives throughout the transfer plan.

A similar graph was proposed in [START_REF] Bocquillon | The data transfer problem in a system of systems[END_REF] to prove that the non-robust dissemination problem with one recipient is polynomial and is equivalent to a max-flow problem (the graph has been slightly simplified because we are considering only one unit at a time). We can prove, in the same way, that a src-snk flow in G(φ, k, r) defines a set of arc-disjoint journeys for transmitting unit k, from one or several sources, to node r, in the evolving graph. These journeys are obtained from the saturated arcs representing a contact in G(φ, k, r), i.e. the arcs having a flow and a capacity of 1. Each unit of flow entering snk in G(φ, k, r) corresponds to a journey from a source of k to node r in the evolving graph. We therefore know that Γ failures cannot be enough to prevent node r from receiving unit k during transfer plan φ if the maximum amount of flow traversing G(φ, k, r) is greater than or equal to Γ + 1 (i.e. if there are at least Γ + 1 arc-disjoint journeys from a source of k to node r in the evolving graph).

In Figure 2b, we report the flow network G(φ, k = 1, r = 5) corresponding to the transfer plan φ described in Figure 2a. Only one unit of flow can traverse the network (using, for example, the bold arcs). This means that the transfer plan is not robust to failures (i.e. φ is not even 0-robust). 6 The minimum cut (depicted in gray) obtained with the Ford-Fulkerson [START_REF] Ford | Maximal flow through a network[END_REF] algorithm informs us that node 5 cannot receive unit 1 if contact σ 5 = (3, 4) fails. This contact is represented by the only arc, namely (3 2 , 4 1 ), which is in the cut-set of that minimum cut. It means that all the journeys from node 1 to node 5 in the evolving graph use contact σ 5 . On the other hand, adding one contact (4, 5) at time 9, such that φ(9) = {1}, would improve the robustness of the solution, cf. the augmenting path (src, 1 0 , 2 1 , 2 2 , 4 2 , 5 2 , snk). The two arc-disjoint journeys in the evolving graph would be (σ 1 , σ 5 , σ 6 ) and (σ 2 , σ 8 , σ 9 ). Formally, this results in the following proposition.

src 1 0 2 0 3 0 4 0 2 1 3 1 2 2 3 2 4 1 4 2 5 0 5 1 5 2 snk ∞ ∞ ∞ ∞ ∞ ∞ 1 1 1 1 1 1 1 1 ∞ ∞ ∞ ∞ 1 σ 9 minimum cut
Proposition 3.1. Let φ be a valid transfer plan. φ is Γ-robust if and only if, for all datum units k ∈ D and all recipient nodes r ∈ R, there exists a src-snk flow of value Γ + 1 in transportation network G(φ, k, r).

Proof. We want to show that, given a datum unit k ∈ D and a recipient node r ∈ R, Γ failures are not enough to prevent r from receiving k if and only if there exists a src-snk flow of value Γ + 1 in G(φ, k, r). We will assume below that the maximum amount of flow traversing the network is finite. Note though that it will be infinite (and therefore greater than Γ + 1) if and only if r is a source of k, i.e. if and only if even an infinite number of failures would not be enough to prevent r possessing k at the end of the sequence of contacts σ.

The condition is obviously sufficient, since Γ failures cannot be enough to invalidate the Γ + 1 journeys, in the evolving graph, which correspond to a flow of Γ+1 in the flow network G(φ, k, r), and which enable node r to receive unit k.

To show the condition is necessary, we use the well-known max-flow/min-cut theorem, which states that, in network G(φ, k, r), the maximum amount of flow passing from src to snk is equal to the minimum capacity of a src-snk cut, i.e. to the minimum total capacity of the arcs which if removed would disconnect src from snk. Only arcs representing a contact, with a finite capacity of 1, can belong to the cut-set of such a cut. It follows that a minimum src-snk cut in G(φ, k, r) corresponds to a minimum set of contacts which if removed would disconnect the sources of unit k from node r in the evolving graph. If φ is Γ-robust, the cardinal of this set is always greater than or equal to Γ + 1.

On a practical level, Proposition 3.1 gives a polynomial time algorithm for checking whether a transfer plan is Γ-robust. For each datum unit and each recipient, we solve a max-flow problem to verify that there exist Γ + 1 mutually arc-disjoint journeys linking a source of this datum unit to this recipient in the evolving graph. This test runs in O(u|R|(Γ + 1)(n + m)) time since, for each pair (k, r) ∈ D × R, we need to find Γ + 1 augmenting paths in a network that contains at most 1 + n + 2m arcs.

This proposition is the basis of the enumeration procedure that we propose in the following section. It enumerates the solutions such that Γ + 1 journeys connect the sources of each datum unit to each recipient node in the evolving graph.

Enumeration procedure

The most naive method for enumerating the set of all Γ-robust transfer plans is to enumerate the set of all valid transfer plans and to retain only Γ-robust solutions. To this end, we propose to set the transfers in the order of the sequence σ, from φ(1) to φ(m). At each node of the search tree, the first transfer φ(c) that is not yet fixed is selected, and one branch is created for each possible value, that is one branch for each datum unit k ∈ O c-1 s c (S * , φ) (failures are ignored at this point), and one additional branch for the null transfer. The algorithm proposed in Section 3.1 is used to filter non-robust solutions.

Unfortunately, such an approach means exploring the entire search space (exponential in size). To avoid this, we propose generalizing the dominance rules that we proposed in [START_REF] Bocquillon | Modeling elements and solving techniques for the data dissemination problem[END_REF]. It is recalled that dominance rules yield conditions on which a subset of the search space considered to solve the problem can be ignored. A dominant set of solutions is a subset of the search space that -if the search space contains at least one feasible solution -contains at least one optimal solution. Thus, enumerating any dominant set of solutions is sufficient to solve the problem. Of course, the smaller this set, the better. We refer to [START_REF] Jouglet | Dominance rules in combinatorial optimization problems[END_REF] for a comprehensive study on this concept.

Robust-minimal transfer plans

First, it will be remarked that some transmissions may be redundant. A same node can receive more than Γ + 1 times the same unit. From an operational point of view, resources are wasted, and from a computational point of view, taking such solutions into account significantly enlarges the search space. It is obvious that such transfers are not desirable.

Hence the definitions below and the ensuing dominance rule. In practice, a transfer φ(c) = {k} is then robust-improving if and only if the maximum amount of flow from src to snk in transportation network G(φ, k, r c ) does not exceed Γ + 1 and is larger when we consider transfer φ(c) than when we only consider the first c -1 contacts (than when the capacities of the arcs corresponding to a contact σ t with t ≥ c are set to 0). Definition 3.2. A transfer plan φ is robust-minimal if and only if all its transfers are null or robust-improving.

In Figure 2, transfer φ( 6) is robust-improving, because it "opens" the first journey to node 5 in the evolving graph. Transfer φ( 7) is not robust-improving, since adding or removing arc (4 1 , 5 2 ) does not increase the amount of flow that can traverse G(φ, 1, 5). If we set φ(7) = ∅, φ becomes robust-minimal. It remains robust-minimal if we consider φ(9) = {1} (since this transfer is robust-improving).

Proposition 3.2. The set of robust-minimal transfer plans is dominant.

Proof. Let φ be a valid non-robust-minimal transfer plan. So there exists at least one transfer φ(c) which is neither null nor robust-improving. Thus, the transfer plan φ -obtained by copying φ and by setting φ (c) = ∅ -has exactly the same dissemination length as φ, i.e. λ Γ (φ ) = λ Γ (φ). This process is to be repeated as long as the new transfer plan is not robust-minimal.

Robust-strictly-active transfer plans

In many cases, some transmissions can be postponed without affecting the optimilaity of the solution. This flexibility significantly enlarges the search space and is not desirable.

Hence the following dominance rule. Proof. Let φ be a non-robust-strictly-active transfer plan, i.e. there exists a non-robust-improving transfer φ(c), c ∈ {1, 2, . . . , m}, and a datum unit k ∈ D such that φ(c) = {k} would be robustimproving. Let then φ be the transfer plan obtained by copying φ, and by setting φ (c) = {k}. The dissemination length of φ is better than or equal to the dissemination length of φ, i.e. λ Γ (φ ) ≤ λ Γ (φ). This process is to be repeated as long as the transfer plan is not robust-strictly-active.

Proposition 3.4. The set of robust-minimal and robust-strictly-active solutions is also dominant (by combining the above proofs).

Enumerating robust transfer plans

Proposition 3.4 states that enumerating robust-minimal and robust-strictly-active transfer plans is sufficient to solve the robust dissemination problem (other transfer plans can be ignored). Therefore -if we use a sequential branching algorithm -we can skip all the branches that do not correspond either to a null transfer or to a robust-improving transfer.

At each node of the search tree, the earliest transfer φ(c) that is not yet fixed is selected, and one branch is created for each possible transfer φ(c) = {k} (k ∈ O c-1 s c ) that "opens" a new journey from a source in k to node r c in the evolving graph. If no such transfer exists, then φ(c) is set to ∅. A transfer plan is Γ-robust when every recipient has received Γ + 1 copies of each unit.

If the flows are stored from one node of the search tree to another, then testing whether a given transfer is robust-improving takes O(n + m) time. Only one iteration of the Ford-Fulkerson [START_REF] Ford | Maximal flow through a network[END_REF] algorithm is required, because a single new arc in G(φ, k, r c ) cannot enable two or more new augmenting paths to be found at the same time (i.e. a single new transfer in the evolving graph cannot "opens" two or more new journeys from a source of k to r c at the same time). Remark 3.1. In practice, only one flow network can be stored in memory. The network defined in Section 3.1 has a structure which depends on the instance that we are examining. In particular, it is only the capacities that differ between two graphs G(φ 1 , k 1 , r 1 ) and G(φ 2 , k 2 , r 2 ) (i.e. the capacities depend only on the partial transfer plan, the datum unit and the recipient node under consideration). Therefore only the capacities -associated with each unit k ∈ D and each node i ∈ N -and the resulting flows need to be stored in a reversible (backtrack-able) data structure. The structure of the graph itself can be static.

A constraint programming approach

In this section we implement the approach proposed in Section 3 for solving the robust dissemination problem. We use constraint programming to be able to utilize pre-implemented tools (filtering algorithms) that make it easy to develop an efficient branch-and-bound procedure. We also propose ad hoc methods to speed up the solving of the problem. All of this will be assessed in Section 5.

Model

In this model, all transfers are required to be robust-improving. Therefore, every recipient node r ∈ R must receive exactly Γ + 1 copies of each unit k ∈ D. At the outset, we assume that r possesses Γ + 1 (resp. 0) copies of

k if k ∈ O r (resp. k O r ).
For each node i ∈ N, T i is defined as the set of time indexes at which the state of i can change, i.e. T i = {0} ∪ {c ∈ {1, 2, . . . , m} | r c = i}. In addition, ∀t ∈ {0, . . . , m}, T i (t) refers to to the last contact occurring before time t where node i is the receiver, i.e.

T i (t) = max {t ∈ T i | t ≤ t}.
The variables of our model are defined as follows:

• ∀k ∈ D, ∀c ∈ {1, . . . , m}, x k,c = 1 if datum unit k is transmitted from node s c to node r c during contact σ c , and x k,c = 0 otherwise.

• ∀i ∈ N, ∀k ∈ D, ∀t ∈ T i , y i,k,t indicates the number of copies of datum unit k possessed by node i after contact σ t . Thus, the domain of these variables is {0, 1, . . . , Γ + 1}.

• ∀c ∈ {1, 2, . . . , m}, a c = 1 if transfer φ(c) is robust-improving, and a c = 0 otherwise.

• ∀i ∈ N, ∀k ∈ D, variable λ i,k represents the delivery length associated with datum unit k and node i, i.e. the date from which node i possesses Γ+1 copies of datum unit k. Its domain is T i ∪ {∞}. λ i,k = ∞ means that i does not recover k during the transfer plan. In practice, we consider ∞ = m + 1.

• ∀i ∈ R, variable λ i = max k∈D {λ i,k } represents the delivery length of recipient node i, i.e. the date from which we are sure that node i possesses all datum units if at most Γ failures occur. Its domain is T i (i has to be served).

• Finally, variable λ = max i∈R {λ i } represents the dissemination length of the transfer plan. Its domain is i∈R T i ⊆ {0, 1, . . . , m}.

Remark 4.1. y-variables are indexed with sets T i rather than set {0, . . . , m}. However, we may easily know whether a node i ∈ N possesses a datum unit k ∈ D at any index t ∈ {0, 1, . . . , m}, since y i,k,T i (t) = 1 if and only if node i possesses datum unit k after the first t contacts.

Minimizing the dissemination length leads to the following objective.

λ * = min λ (1)
The constraints are written as follows (these constraints alone are not sufficient to ensure that the transfer plan is Γ-robust):

• Each node i ∈ N initially possesses a subset O i of datum units:

∀i ∈ N, ∀k ∈ D | k ∈ O i , y i,k,0 = Γ + 1 (2) ∀i ∈ N, ∀k ∈ D | k O i , y i,k,0 = 0 (3)
• The transfer plan must be valid (sending nodes must possess the units that they transmit):

∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, x k,c ≤ y s c ,k,T i (c-1) (4)
• Nodes possess a datum unit from the time they receive it:

∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, y r c ,k,T i (c-1) + x k,c = y r c ,k,c (5)
• At most one datum unit can be transferred during each contact:

∀c ∈ {1, 2, . . . , m}, k∈D x k,c = a c (6)
• λ i,k is the delivery length associated with datum unit k and node i:

∀i ∈ N, ∀k ∈ D, ∀t ∈ T i , [ y i,k,t < Γ + 1 ] ⇐⇒ [ λ i,k > t ] (7)
Implicit constraints.

No simple constraints exist that would explicitly ensure that the transfer plan is Γ-robust. We ensure this through the branching stage. As mentioned in Section 3.2, to solve the problem, we sequentially fix the transfers. This corresponds to setting x-variables from x k,1 (∀k ∈ D) to x k,m .

1. At each node of the search tree, the earliest transfer φ(c) which is not yet fixed (the smallest index c ∈ {1, 2, . . . , m} such that ∃k ∈ D where x k,c is not yet fixed) is selected. 2. Next, one branch is created for each robust-improving transfer. For each datum unit k ∈ O c-1 s c , if transfer φ(c) = {k} is robust-improving, then a branch is added where x k,c = 1 and ∀p ∈ D\{k}, x p,c = 0. 3. Finally, if no robust-improving transfers have been found, then φ(c) is set to ∅, i.e. ∀k ∈ D, we set x k,c = 0.

To check whether a given transfer is robust-improving, we use the test defined in Section 3.2. Note that the capacities of the transportation network are given by the x-variables for transfers occurring before φ(c), and must be set to 0 for other transfers. In this way, we ensure that the transfer plan is Γ-robust (because other constraints ensure that each recipient receives Γ + 1 copies of each unit). This approach ensures that the transfer plan is both robust-minimal (every transfer is either null or robust-improving) and robust-strictly-active (since robust-improving transfers cannot be postponed).

Remark 4.2. A transfer φ(c) = {k} is necessarily robust-improving if there exist more arc-disjoint journeys from a source of datum unit k to node s c than from a source of k to node r c . In such a case no flows need to be computed and a c can be set to 1. In practice, we can use the following constraint: ∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, if [ y s c ,k,T sc (c-1) > y r c ,k,T rc (c-1) ] then [ a c = 1 ].

Ad hoc procedures.

As regards the robust dissemination problem, we have discussed the key concepts and models. The solving process may be speeded up through the use of ad hoc procedures (typically through the use of specific filtering algorithms).

To start with, note that almost all approaches that were proposed for the non-robust case [START_REF] Bocquillon | A constraint-programming-based approach to solve the data dissemination problem[END_REF] can be generalized straightforwardly to the robust case. These remain applicable provided that datum units and their copies are taken into consideration, i.e. provided that we correctly take into account the requirement that each recipient receives Γ + 1 copies of each datum unit, and not just one. In Sections 4.2 through 4.4 we summarize the key ideas behind all these approaches, but we refer the reader to [START_REF] Bocquillon | A constraint-programming-based approach to solve the data dissemination problem[END_REF] for further details (cf. Propositions 5.1, 5.2, 5.3 and 5.5). In Section 4.5 we propose and discuss a new ad hoc procedure.

Lower bounds

First, the so-called weak lower bound becomes: Proposition 4.1. Let i ∈ R be a recipient node, and α = (Γ + 1) × (u -|O i |) be the number of datum units (including copies) that i has to receive during the transfer plan. Let σ x ∈ σ denote the α th contact σ c = (s c , i) during which a unit k ∈ D\O i can be transferred to node i (i.e. such that variable x k,c is not set to 0). When this index does not exist (when it remains less than α contacts fulfilling the condition), we consider that x = ∞. x is a lower bound for λ Γ i (φ) and λ Γ (φ) (i.e. λ ≥ λ i ≥ x in the model).

This lower bound is trivial, but it can be improved if one can prove that there exists no valid transfer plan allowing node i to receive the α datum units it needs with only the first α available contacts. We can actually add some contacts while the condition is not respected. Each test can run in polynomial time by solving an assignment problem. This corresponds the so-called strong lower bound, which is tighter, but which is also more complicated to compute.

Symmetry-breaking constraints

Let us consider the example on the left of Figure 3. At time t = 3, datum units 1 and 2 share the same sources (nodes 1, 2 and 3), i.e. ∀i ∈ N, 1 ∈ O 3 i if and only if 2 ∈ O 3 i . Thus, the role of these datum units can be swapped in the rest of the sequence (see the right half of the figure). That is to say, the sub-branchings (in the evolving graph) corresponding to datum units 1 and 2, and with contacts occurring after contact σ 3 , can be swapped. The dissemination length is not affected by this operation. As a result, it is sufficient to consider one option (either φ(4) = {1} or φ(4) = {2}) out of the two to solve the robust dissemination problem, e.g. we can arbitrarily decide to transmit the datum unit with the lowest index first.

In practice, at each node of the search tree, whenever we are setting a transfer φ(c), we can check whether two units k 1 and k 2 ∈ D (with k 1 < k 2 ) have the same sources. If so, x k 2 ,c can be set to 0, i.e. the branch such that φ(c) = {k 2 } can be ignored, because the branch where φ(c) = {k 1 } will be explored. Figure 3: A symmetry appears between units 1 and 2 when we set φ(4).

Memorization

Let us now move to another symmetry-breaking technique. The latter involves registering the state of the nodes visited in the search tree. This enables branches to be pruned by detecting dominance relationships among the transfer plans under construction.

At each node of the search tree, whenever we are setting a transfer φ(c), we can check whether another transfer plan φ such that ∀i ∈ N, O c-1 i (S * , φ) ⊆ O c-1 i (S * , φ ) has already been visited. If so, the current branch can be pruned. As a matter of fact, from any solution φ that is reachable from the current node, we can build a better or equivalent solution φ by choosing the first c -1 transfers of φ and the last mc + 1 transfers of φ. Transfer plan φ can be ignored because φ has already been visited.

Testing whether ∀i ∈ N, O c-1 i (S * , φ) ⊆ O c-1 i (S * , φ ) is trivial if these sets are represented by bit vectors (only a few boolean operations are sufficient to check it). This computational efficiency makes it possible to store thousands of states and thereby, to improve the performance of the solver significantly.

The look-ahead procedure

In some circumstances, the solver manages to prove that some transfers are necessary even before the sequential branching algorithm needs to choose a value for these transfers (by combining some of the constraints in the model). The corresponding x-variables are then set to 1. In such a case, the first t ∈ {0, . . . , m -1} transfers are fixed and φ(t + 1) is the first unfixed transfer, but there exists a transfer φ(c) = {k}, c ∈ {t + 2, t + 3, . . . , m}, k ∈ D, that has been set by another filtering procedure. Like any other transfer, φ(c) must be robust-improving. This constrains some transfers φ(x), x ∈ {t + 1, . . . , c -1} that have not yet been fixed.

For example, in Figure 4, the solver may deduce that φ(6) = {1} and φ(9) = {1} at the start (since there are only two contacts left for sending two copies of unit 1 to node 6). In Figure 4a, the branch φ(1) = {2} is explored. We assume that the solver has deduced, for any reason, that φ(3) is necessarily equal to {2}. We can easily show that this branch leads to no dominant transfer plan, so it can be pruned immediately. In Figure 4b, the branch φ(1) = {1} is explored. We can show that unit 1 must be transferred to nodes 4 and 5 during contacts σ 5 and σ 7 , so variables x 1,5 and x 1,7 can both be set to 1.

Unfortunately, these constraints are not explicit in the model and specific algorithms must be developed to make such deductions. In this context, we have proposed the so-called look-ahead procedure, which aims to:

1. trigger a backtrack when one can prove that there exists no dominant solution in which transfer φ(c) is robust-improving, 2. prove that some transfers φ(x), x ∈ {t + 1, . . . , c -1} are necessary, and therefore to set the corresponding x-variables to 1.

Space constraints prevent us from describing the look-ahead procedure thoroughly, so readers are referred to [START_REF] Bocquillon | Data distribution optimization in a system of collaborative systems[END_REF] for further details. Note here that the procedure relies on a careful study of the minimum cuts of the transportation networks G(φ, k, r), k ∈ D, r ∈ N, that are described in Section 3.1. The procedure is integrated into the branching algorithm described in Section 3.2.

Computational results

In this section, computational results are reported and discussed. We begin by describing our benchmark, built out of the instances generated for the non-robust dissemination problem, then we look at the results obtained using the different algorithms described in Section 4.

All the instances and the C++ source code discussed below are available online [START_REF]C++ source code[END_REF][START_REF]Instances for both the robust and the original dissemination problem[END_REF].

About the benchmark

To build a "hard" benchmark we propose using the instances that we previously generated for the non-robust dissemination problem.

It is recalled here that instances of the non-robust dissemination problem were generated by a destruction-construction heuristic designed to increase the hardness of an instance. This procedure is initialized with an instance chosen at random, then seeks to generate harder and harder instances by removing the least relevant contacts (i.e. the contacts removed by a trivial preprocessing procedure), so that new ones can be added elsewhere without increasing the size of the instance. A few contacts are randomly renewed in order to introduce diversity. At each iteration, the instance is solved with CPLEX. After an arbitrary number of iterations, the instance that required the most CPU time is returned. This was shown to produce some challenging instances of which we would like to keep the structure. For further details we refer to [START_REF] Bocquillon | Modeling elements and solving techniques for the data dissemination problem[END_REF].

Given Propositions 2.1 and 3.1, we expect an instance of the robust dissemination problem to be as difficult as an instance of the dissemination problem having roughly Γ times as many units (keeping constant the number of nodes and the number of contacts). Consequently, we propose reusing the instances generated for the dissemination problem, reducing the number of datum units so that the previous number of units is roughly equal to (Γ + 1) × u in the new instance.

We are faced with a familiar trade-off between a larger value of (Γ + 1) × u, where feasible transfer plans are harder to find, but proofs of infeasibility are usually easier, and a smaller value of (Γ + 1) × u, where feasible transfer plans are easier to find, but proofs of infeasibility may be harder. It will consequently be difficult to prove that any solution is optimal.

The benchmark is described in Table 1. Each class is characterized by the number nbinst of instances it contains, the required level of robustness Γ, the number of units u, and the number of nodes n in these instances. The average number rec of recipients i ∈ R, the average number src of source nodes i ∈ N such that O i ∅, and the average number m of contacts in every class are also reported. In column from, we indicate the class(es) (originally used for the dissemination problem) from which the new instances are built.

Numerical results

Like in [START_REF] Bocquillon | A constraint-programming-based approach to solve the data dissemination problem[END_REF][START_REF] Bocquillon | Modeling elements and solving techniques for the data dissemination problem[END_REF], the computations reported in this paper were all performed on a server equipped with 16 × 6 cores (running at 2.67Ghz) and 1TB RAM. Algorithms were all implemented in C++. Constraint-programming models were solved using CP-Optimizer, a commercial solver developed by IBM-Ilog. The multithreading features proposed by the library were systematically deactivated, because the use of concurrent optimizers led to unstable results (different executions of the same computation often led to different results in terms of CPU time), which prevented reliable comparisons between our methods. Instances were therefore solved using a deterministic sequential algorithm with a one-hour time limit.

All our results tables (see below) feature the following metrics:

1. solved (-%) indicates the percentage of instances solved to optimality (a feasible solution was proved to be optimal or the instance was proved to be infeasible). 2. feas (-%) indicates the percentage of instances where optimality was not proved, but for which the solver found at least one feasible solution within the one-hour time limit. It follows that 100%solvedfeas indicates the ratio (-%) of instances for which the solver neither found a feasible solution nor showed the instance to be infeasible.

To achieve better results, we need to consider the ad hoc procedures proposed in Sections 4.2 through 4.4, namely the weak (wlb) or the strong (slb) lower bounds, the symmetry-breaking constraints (sym), memorization (mem) and/or the look-ahead procedure (la).

When these procedures are considered one by one, we remark that the weak lower bound is the element that has the greatest impact on the performance of the solver (see column wlb in Table 2). However, we might wonder whether the strong lower bound really is relevant for this problem, given that the percentage of instances solved to optimality tends to be worse in column slb than in column wlb. The strong lower bound is tighter, but also has a higher time complexity than the weak lower bound. As is often the case, there is a balance to be struck between heavy computations and tight bounds versus light computations and weak bounds. Experimental results show that the weak lower bound is more effective, in practice, than the strong lower bound.

Memorization and symmetry-breaking constraints are also seen to be very effective. Using these features (together with the weak lower bound) enables more than 70% of the benchmark to be solved (see columns wlb+mem and wlb+mem+sym in Table 2). The impact of the lookahead procedure is certainly more limited, but is worth mentioning (cf. wlb+mem+sym+la).

Conclusion

This paper investigates the problem of transferring data through a deterministic delay-and disruption-tolerant network. We address the problem of finding a Γ-robust transfer plan (routing scheme), i.e. a valid transfer plan that guarantees that the recipient nodes always receive all the datum units, even if some transfers -at most Γ -fail. We believe that this approach covers a wide range of constraints that are to be found in real applications.

We propose a constraint-programming-based algorithm This algorithm rests on a necessary and sufficient condition for a transfer plan to be robust. Promising numerical results are reported. We show that specific ad hoc filtering algorithms, e.g. some lower bounds, are required for the model to be solved efficiently.

Figure 1 :

 1 Figure 1: An instance of the non-robust dissemination problem (Γ = 0), a solution and the associated evolving graph.

  (a) a transfer plan φ to deliver datum unit 1 from node 1 to node , 2, . . . , 8}, φ(c) = {1} the corresponding flow network G(φ, k = 1, r = 5)

Figure 2 :

 2 Figure 2: The flow network used to show the robustness of a transfer plan.

Definition 3 . 1 .

 31 Transfer φ(c) = {k}, c ∈ {1, 2, . . . , m}, k ∈ D, is robust-improving if and only if it improves the level of robustness associated with unit k and node r c (i.e. the minimum number of failures required to prevent r c from receiving datum unit k) without, however, exceeding Γ.

Definition 3 . 3 .Proposition 3 . 3 .

 3333 A transfer plan φ is robust-strictly-active if and only if all transfers are robustimproving when possible, i.e. ∀c ∈ {1, 2, . . . , m}, if ∃k ∈ O c-1 s c such that φ(c) = {k} is robustimproving, then φ(c) is robust-improving. The set of strictly-active transfer plans is dominant.

10 Figure 4 :

 104 Figure 4: The look-ahead procedure (Γ = 1, 6 ∈ R and t = 1).

  a 12 } of arcs. a 10 and a 11 cannot be in the same covering branching, otherwise vertices c, d, e and f could not be reached. Let us suppose that a 10 ∈ B 1 and a 11 ∈ B 2 . This means that arc a 4 ∈ B 1 and a 1 ∈ B 2 . To reach node c, since a 2 cannot follow a 10 and a 5 cannot follow a 11 in a valid journey, we have to put a 2 in the covering branching containing a 1 , so a 2 ∈ B 2 , and a 5 in the covering branching containing a 4 , so a 5 ∈ B 1 . To reach node d, we have to put a 6 in one covering branching and a 12 in the other one. If a 6 ∈ B 1 and a 12 ∈ B 2 , then a 7 have to be in B 1 (since it cannot follow a 12 in a valid journey) and a 3 have to be in B 2 (it can follow a 1 ). Thus, none of a 8 , a 9 can be added to B 2 , because a 9 cannot follow a 11 and a 8 cannot follow a 12 in a valid journey. The same contradiction arises with a 10 ∈ B 2 , a 11 ∈ B 1 or with a 6 ∈ B 2 , a 12 ∈ B 1 .

Table 1 :

 1 The benchmark generated for the robust dissemination problem.

	name	from	nbinst	Γ	u	n	rec	src	m
	1r2u20n	4u20n	41	1	2	20	18	1	366
	1r2u50n	4u50n+5u50n	49	1	2	50	44	1	717
	1r2u100n	4u100n	20	1	2	100	87	2	1720
	1r5u10n	10u10n	16	1	5	10	6	2	197
	1r25u10n	50u10n	16	1	25	10	6	2	750
	1r50u10n	100u10n	6	1	50	10	7	4	2000
	2r2u50n	2r5u50s	23	2	2	50	50	1	726
	2r3u10n	10u10n	16	2	3	10	6	2	197
	2r17u10n	50u10n	16	2	17	10	6	2	750
	2r34u10n	100u10n	6	2	34	10	7	4	2000
	3r2u10n	10u10n	16	3	2	10	6	2	197
	3r13u10n	50u10n	16	3	13	10	6	2	750
	3r25u10n	100u10n	6	3	25	10	7	4	2000

Acknowledgement

These works are financed by the Conseil Régional de Picardie, and carried out in the framework of Labex MS2T (Maîtrise des systèmes-de-systèmes technologiques), funded by the French government through the Investments for the Future program, and managed by the National Agency for Research (ANR-11-IDEX-0004-02).

3. cpu (-s) is the average solution time. This metric is calculated only on the solved% of the instances that were solved to optimality within the one-hour time-limit.

All comparisons between algorithms are therefore made with respect to metrics that have a clear hierarchy of relevance, where solved is the most important information. If solved is the same, the next most important information to take into account is feas and finally cpu. Note that value "-" means that the corresponding metric is meaningless (e.g. feas is always equal to 0% if solved = 100%) or cannot be calculated (e.g. cpu cannot be calculated if solved = 0%).

Column none in Table 2 contains the computational results obtained using the model described in Section 4.1 and the branching algorithm described in Section 3.2 (with no ad hoc procedures).

We observe that only 20% of the benchmark was solved to optimality, but that feasible robust transfer plans were found for approximately 70% of the remaining instances. This shows that the benchmark is sufficiently challenging, and that the solver (CP-Optimizer) can run into difficulties, even for small instances.