Giovanni Neglia
email: giovanni.neglia@inria.fr

Xiaolan Zhang
email: xzhang@fordham.edu

James F Kurose
email: kurose@cs.umass.edu

Don Towsley
email: towsley@cs.umass.edu

Haixiang Wang
email: ahawang@fordham.edu

On Optimal Packet Routing in Deterministic DTNs *

In this paper, we investigate the problem of determining the routing that minimizes the maximum/average delivery time or the maximum/average delivery delay for a set of packets in a deterministic Delay Tolerant Network, i.e. in a network for which all the nodes' transmission opportunities are known in advance. While the general problem with multiple sources and multiple destinations is NP-hard, we present a polynomial time algorithm that can efficiently compute the optimal routing in the case of a single destination or of a single packet that needs to be routed to multiple destinations.

Introduction

Deployed in areas with limited infrastructure support, many vehicular networks [START_REF] Doria | Providing Connectivity to the Saami Normadic Community[END_REF][START_REF] Burgess | MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks[END_REF][START_REF] Hull | CarTel: A Distributed Mobile Sensor Computing System[END_REF], rely on peer-to-peer connectivity between wireless radios to support data communication. Due to limited transmission power, fast node mobility, sparse node density and frequent equipment failures, many such networks exhibit only intermittent connectivity, and can be characterized as Disruption Tolerant Network (DTN, or Delay Tolerant Network ). Endto-end communication in DTNs adopts a so-called "store-carry-forward" paradigm [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF]: a node receiving a packet buffers and carries the packet as it moves, passing the packet on to other nodes that it encounters. The packet is delivered to the destination when the destination meets a node carrying the packet.

A plethora of works have proposed DTN routing schemes to operate in the case of zero or partial knowledge about future transmission opportunities (e.g. [START_REF] Spyropoulos | Spray and wait: an efficient routing scheme for intermittently connected mobile networks[END_REF][START_REF] Haas | A New Networking Model for Biological Applications of Ad Hoc Sensor Networks[END_REF][START_REF] Spyropoulos | Efficient Routing in Intermittently Connected Mobile Networks: The Multi-copy Case[END_REF][START_REF] Balasubramanian | Replication Routing in DTNs: A Resource Allocation Approach[END_REF]): some explored the trade-off between routing performance and resource consumption, while others attempted to optimize routing performance under certain resource constraints. On the other hand, other works took a different approach and studied the routing under the assumption of a full knowledge of network contacts, i.e. in deterministic DTNs. While such assumption is realistic in some specific scenarios like interplanetary networks [START_REF] Burleigh | Delay-Tolerant Networking: an Approach to Interplanetary Internet[END_REF] or transport networks [START_REF] Burgess | MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks[END_REF], these works have also a theoretical interest, because they shed light on the fundamental hardness of the problem [START_REF] Balasubramanian | Replication Routing in DTNs: A Resource Allocation Approach[END_REF], and on best case performances [START_REF] Zhang | Study of a bus-based disruption tolerant network: Mobility modeling and impact on routing[END_REF][START_REF] Chaintreau | The Diameter of Opportunistic Mobile Networks[END_REF], and can be used in the learning phase of a practical scheme [START_REF] Guo | Prediction Assisted Single-copy Routing in Underwater Delay Tolerant Networks[END_REF].

This paper falls within the second category and studies the packet routing problem in deterministic DTNs. Given a group of packets to be routed in such a network, we consider as performance metric both the delivery time, i.e. the absolute time at which a packet is delivered to the destination, and the delivery delay, i.e. the difference between the packet delivery time and the packet generation time at the source. For both metrics, we consider as goal both the minimization of the maximum value across all the packets and the minimization of the average value. This leads to four different optimization problems that we study in a common framework.

Our work build upon the seminal work by Hay and Giaccone [START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF], which uses the event-driven graph1 reduction to map several DTN routing problems to flow problems in static graph, including the minimum delay path and the maximum bandwidth routing problems for a single source-destination pair. As the authors noted, the case of DTN routing with multiple source/ destination pairs can be mapped to multi-commodity flow problem, which can be solved using linear programming if fractional flows are allowed. In contrast, in this paper we focus on the routing of unsplittable packets leading to integral multi-commodity flow problems which are much harder problems.

The main contributions of this paper are summarized as below: • We extend existing results to prove the NP hardness of the four optimization problems in the general case with multiple sources and multiple destinations.

• For the case of a single destination or a single packet to be delivered to multiple destinations, we show that a polynomial-time algorithm exists that can provide an optimal routing for three of the problems (all but minimizing the maximum delivery delay).

• We show how our algorithm can be used to efficiently characterize a real mobility trace collected from DieselNet.

The algorithm presented in this paper was originally developed in the framework of our research on network coding to calculate the minimum delivery time for a set of packets. For this reason a sketch of the algorithm appears in our work [START_REF] Zhang | Benefits of Network Coding for Unicast Application in Disruption Tolerant Networks[END_REF]. In comparison to [START_REF] Zhang | Benefits of Network Coding for Unicast Application in Disruption Tolerant Networks[END_REF], this paper investigates the complexity of a general class of problems, presents a more complete description of the algorithm, showing how it can be used to determine the actual scheduling that minimizes not only the maximum delivery time, but also the average delivery time and the average delivery delay.

The remainder of this paper is structured as follows. In Sec. 2, we introduce the network model and performance metrics considered in this paper. Sec. 3 presents the problems we study, the complexity results for the different cases and our algorithm. In Sec. 4 we show some characteristics of Diesel-Net traces obtained through our algorithm. Finally, Sec. 5 concludes this paper. Due to space constraints, the proofs can be found in the companion technical report [START_REF] Neglia | On Optimal Packet Scheduling in Deterministic DTNs[END_REF].

Background

We consider a set of mobile nodes, denoted as V, moving independently in a closed area. Each node is equipped with a wireless radio with a com-mon transmission range so that when two nodes come within transmission range of each other-they have a contact-they can exchange packets. We refer to the list of node-to-node contacts, sorted in temporal order, as a DTN contact trace, denoted as L = l 1 , l 2 , l 3 , .... Each contact, l i , is a tuple (t(l i ), s(l i ), r(l i ), b(l i )) where t(l i ) denotes the time of the contact, s(l i ) and r(l i ) denote respectively the sending and the receiving node of the contact, and b(l i ) denotes the number of packets that can be transmitted during the contact2 . We assume each node can store an unlimited number of packets destined for itself, but can only carry a limited number of packets for other nodes. We represent the buffer constraint as a function, B : V → N where B(u) is the number of relay packets that node u can carry.

A contact trace can be depicted as a temporal network [START_REF] Kempe | Connectivity and Inference Problems for Temporal Networks[END_REF], a multi-graph T (L) = V, E where each edge in E represents a contact l ∈ L. The edge is directed and labeled with a pair, (t(l), b(l)), i.e., the time of the contact, and the number of packets that can be exchanged using the contact. For example, Fig. 1(a) illustrates the temporal network model for a contact trace of a DTN with four nodes during the time interval [0, 24].

We use the contact trace in Fig. 1(a) to illustrate the construction of the event-driven graph [START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF] G(L, B) given a contact trace L and buffer constraints B(•) (the graph is shown in Fig. 1(b)). For each contact l = (t, u, v, b) ∈ L, two nodes (u, t) and (v, t) are added to the graph G, respectively denoting the sending and receiving event of the contact. A directed inter-node edge (depicted as a horizontal line in Fig. 1(b)), labeled with b, connects node (u, t) to node (v, t), denoting that up to b packets can be transmitted from node u to v at time t. If two consecutive contacts involving node u occur at t 1 and t 2 (> t 1 ), a directed intra-node edge connecting node (u, t 1 ) to node (u, t 2 ) is added to graph G, with a capacity equal to B(u), i.e., the maximum number of relay packets node u can store (this edge is depicted as a vertical line in the figure).

The following proposition is a restatement of Theorem To see this, we note that the value of a flow on an inter-node edge equals the number of packets sent during the corresponding contact whereas the value of a flow on an intra-node edge corresponds to the number of packets being carried by the node during the corresponding time interval. We assume that a set of packets M = {m 1 , m 2 , ..., m k } propagates in the network. Each packet can be denoted as m i = (s i , d i , t i ), where s i , d i and t i denote respectively the source, the destination, and the generation time of packet m i3 . In this paper, we focus on routing performance in terms of delivery time or delivery delay. Let the delivery time of packet m i be T i for i = 1, 2, . . . k. We consider the following four metrics defined over the whole set of packets:

• The Maximum Delivery Time (MDT) is defined as the time instant at which the last packet in the set is delivered to its destination, i.e. T M = max 1≤i≤k T i .

• The Maximum Delivery Delay (MDD) is defined as

D M = max 1≤i≤k (T i -t i ).
• The Average Delivery Time (ADT) is defined as

T a = k i=1 T i /k.
• The Average Delivery Delay (ADD) is defined as

D a = k i=1 (T i -t i )/k.
Depending on the specific application one or the other of these metrics may be more relevant.

Minimal Time/Delay Routing in DTNs

We want to determine the optimal routing for each of the four metrics defined above. We observe that minimizing ADT and minimizing ADD are equivalent problems because the two metrics differ only by a constant value ( i t i /k). Apart from this, the three optimization problems (min MDT, min MDD, min ADT/ADD) are different (some examples are shown in [START_REF] Neglia | On Optimal Packet Scheduling in Deterministic DTNs[END_REF]).

We start our study by establishing the NP-hardness of these problems in the general scenario with different sources and different destinations. Proposition 3.1 Given a contact trace L, and a set of packets M, the following problems are all NP-hard:

1. finding a feasible routing that achieves minimal MDT, 2. finding a feasible routing that achieves minimal ADT/ADD, 3. finding a feasible routing that achieves minimal MDD.

The NP-hardness of MDT minimization has already been proven in [START_REF] Balasubramanian | Replication Routing in DTNs: A Resource Allocation Approach[END_REF] (Lemma 1). In the companion technical report [START_REF] Neglia | On Optimal Packet Scheduling in Deterministic DTNs[END_REF], we use mainly the same technique to prove the other results.

In what follows we first present a polynomial-time algorithm (Sec. 3.1) to determine the routing that minimizes MDT in the special case where all packets are destined to the same destination. We then shows in Sec. 3.2 how this routing also minimizes ADT (or ADD), even if the two problems are not equivalent. We conclude this section by discussing a few extensions in Sec. 3.3.

MDT Routing Algorithm for Common Destination

Although finding the MDT for a set of packets is generally a NP-hard problem, this problem is solvable in polynomial time under the special case where all packets in the set are destined to the same node. We discuss this special case and present our algorithm in this section.

Preliminary

Under the assumption that every packet m i ∈ M is destined to a common destination, we can denote packet m i as (s i , d, t i ), where d is the common destination.

We first discuss how to determine whether the set of packets M can be delivered given contact trace L and under buffer constraints B(•) using the event-driven graph model. In order to answer this question, we extend the event-driven graph G(L, B) as follows. First, we add a super source node src and a super destination node dest into the graph. Then, for each packet m i = (s i , d, s i ) ∈ M, a packet generation node (s i , t i ) is added into the graph, and connected to node (s i , t i,0 ) using an intra-node edge, where t i,0 is the time of the first contact after t i involving node s i . Next, we connect node src to each packet generation node using an intra-node edge with capacity 1, denoting that one packet is generated at each source node 4 . We connect all nodes involving node d to node dest with an intra-node edge with a capacity of k. Finally, we also change to k the capacity of intra-node edges for the destination node d, as we assume nodes have sufficient buffer space to store packets destined for them. We denote the resulting graph as G(L, B, M). For example, Fig. 2 plots the event-driven graph for the set of packets {(1, 4, 0.5), (2, 4, 0.3)} for the DTN trace depicted in Fig. 1.

Based on Proposition 2.1, the set of packets M can be delivered given contact trace L and buffer constraints B(•) if and only if there is a flow of value k from src to dest in G(L, B, M). We therefore have the following proposition: the last contact in L min is the minimum MDT, and this flow in G corresponds to a schedule that achieves the minimum MDT.

Algorithm Description

Our minimum MDT routing algorithm (Alg.1) intertwines the steps of searching for L min with the iterations of the Ford-Fulkerson algorithm for the maximum-flow problem [START_REF] Kleinberg | Algorithm Design[END_REF].

Initially, no contact has been added into the event-driven graph, and G f = G(∅, B, M) contains a super source node src, k packet generation nodes (s 1 , t 1 ), ..., (s k , t k ), and a super destination node dest, with the node src connected to each packet generation node with an edge of capacity 1. Subsequently, the algorithm iterates the expand graph phase and the find max-flow phase until the value of the flow reaches k or all contacts in L have been processed.

In the expand graph phase, the graph G f is expanded by considering events from L in time order, until FindPath (G f , src, dest) finds a new path with a non-zero residual capacity5 (via breadth-first search) from node src to node dest. Here Grow (G f , B, l) expands G f by adding the contact l ∈ L, following the procedure described in Sec. 2.

Once a path is found, the algorithm enters the find max-flow phase where the flow is augmented until the max-flow from node src to dest in G f is determined. The procedure UpdateResidualGraph (G f ,f ,P ) implements the following two steps of the Ford-Fulkerson algorithm: augmenting the flow f along path P and updating the residual graph G f . The return value b is the increment of the flow value due to path P . While the Ford-Fulkerson algorithm used here is not the most efficient max-flow algorithm, it allows us to incrementally augment the flow instead of starting the maximum flow calculation from scratch every time the graph is expanded.

When the outer while loop terminates, either the flow value reaches k or all contacts have been processed. The algorithm calls the procedure Con-structScheduleFromFlow (f ) to construct a packet routing schedule from the flow f , and determines the MDT as the time of the last contact considered (if all k packets are delivered). The above two values are returned, together with the flow value supported (i.e., the number of packets that can be delivered at the end of the contact trace).

Let L ′ be the subsequence of the contact trace L considered up to termination, the computational complexity of Alg. 1 is O(k|L ′ |) (see [START_REF] Neglia | On Optimal Packet Scheduling in Deterministic DTNs[END_REF] for the derivation).

Minimum ADD/ADT Routing

In this section we prove that the routing determined by Alg. 1 also guarantees minimum ADD (or ADT). This is a consequence of the following result (the proof is in [START_REF] Neglia | On Optimal Packet Scheduling in Deterministic DTNs[END_REF]):

Lemma 1 Let F (t) denote the fraction of packets delivered by time t with the routing returned by Alg. 1. Consider any other routing and denote as G(t) the corresponding function. We have F (t) ≥ G(t) for t > 0.

It follows from this lemma that the routing returned by Alg. 1 also guarantees minimum ADT (or ADD). In fact the average delivery time can be calculated as

∞ 0 1 -F (t)dt and ∞ 0 1 -G(t)dt respectively for the two routing. As F (t) ≥ G(t), we have ∞ 0 (1 -F (t))dt ≤ ∞ 0 (1 -G(t))dt.

Extensions

We briefly mention a few extensions that are detailed in [START_REF] Neglia | On Optimal Packet Scheduling in Deterministic DTNs[END_REF]. First, the same algorithm can be adapted to deal also with the case where a single packet has to be delivered to multiple destinations. Second, in these specific cases (single destination or single packet) other different optimization problems can be formulated on the event-driven graph as integer programming problems, that can still be solved in polynomial time through standard linear programming (because the solution of the relaxed problem can be guaranteed to be integer). Finally, similar NP-hardness results can be proven for the case of multiple multicast sessions.

Simulation Studies

In this section, we demonstrate how our algorithm allows us to characterize a contact trace. For our case study, we use the trace collected from the UMass DieselNet [START_REF] Burgess | MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks[END_REF] 30-bus testbed in 2006. This trace details for each busto-bus contact the time of the contact, the transmitting bus, the receiving bus, and the number of bytes transferred. The number of packets that can be transmitted during the meeting has been obtained by dividing the total number of bytes by 1400.

We investigate the following question, given a file generated at a bus and destined to another bus, what is the minimum delivery time taking advantage of opportunistic transmission opportunities among the different buses? We answer this question by considering the minimal delivery time for a set of k packets with common source and destination, generated at the same time instant. Each packet has size 1400 bytes and the number of packets ranges between 10 and 200. We assume that the set of packets is not delivered by the end of day (i.e., 7 pm each day) will be dropped, or delivered by an alternative way (e.g. when the bus returns to the garage). In Fig. 3 we plot minimal MDT and ADD for a set of packets generated at bus 3029 and destined to bus 3038 at different time instants of the day. Due to the piece-wise linear property of these metrics in terms of packet generation time 6 , we only need to use our MDT-routing algorithm on a finite number of generation time instants. As expected, the MDT exhibits a step-curve: later packet generation does not affect the MDT until a critical contact is lost and the routing has to change leading to a later delivery. In terms of delay the curve first decreases (the delivery time does not change but the packet generation time increases), and then jumps to a larger value when the routing changes. We observe that no set of packets generated after 1pm can be delivered by 7pm. The numerical results show how even optimal routing in DieselNet testbed exhibits large delays, that vary significantly according to the generation time.

Our algorithm can also be used to find out the minimal time to collect sensor data from multiple buses to a single sink. Due to the page limit, the result is not shown here.

Conclusions

In this paper, we have presented a polynomial time algorithm that can compute optimal routing for a group of packets in a deterministic Delay Tolerant Network in terms of maximum delivery time, average delivery time and average delivery delay. As future work we plan to compare this algorithm to other possible approaches (like more efficient maximum flow algorithms coupled with a binary search of the minimal length contact sequence) and to extend it to more general performance metrics that take into account also energy consumption. P ←FindPath(G f , src, dest)

15:

until P = null 16:

// Find Max-Flow Phase

Figure 1 :

 1 Figure 1: Graph representations of a DTN contact trace.

Proposition 3 . 2 Figure 2 :

 322 Figure 2: Event-driven graph G(L, B, {(1, 4, 0.5), (2, 4, 0.3)}) for calculating minimum MDT schedule for packets (1, 4, 0.5), (2, 4, 0.3), with B(u) = 2, u ∈ V. The newly added edges are drawn with dashed lines.

Figure 3 :

 3 Figure 3: Delivery time and delay for a set of packets sent from bus 3029 to bus 3038 at different time on 4/4/2006

Algorithm 1 : repeat 11 : 13 :

 11113 MIN MDT ROUTING (L, B, M ), find minimum MDT routing for the set of packets, M = {(s 1 , d, t 1 ), (s 2 , d, t 2 ), ..., (s k , d, t k )}, under contact trace L and buffer constraints B(•) 1: Input: L, B, M 2: Output: S, k d , T M // schedule, num. of pkts delivered, minimum MDT 3: L r ← L, x ← 0, P ← ∅, 4: f (e) ← 0 for every edge e in G(∅, B, M) 5: G f ← G(∅, B, M), // initial residual network 6: while x < k and L r = ∅ do graph until a contact to node d is found 10l ←pop(L r ) // extract next contact from L r 12:G f ←Grow(G f , l, B), G f ← G ′ f until r(l) = d //until the receiving node of contact l is d 14:

17 :

 17 while P = null and x < k do 18:(G ′ f , f ′ , b) ← UpdateResidualGraph (G f , f, P ) 19: G f ← G ′ f , x ← x + b 20: f ← f ′ //update the flow 21: P ←FindPath(G f , src, dest) 22: end while 23: end while 24: S ← ConstructScheduleFromFlow (f ) 25: k d ← x // the number of pkts delivered 26: T M ← t(l) // time of last contact considered 27: return S, k d , T M

The space-time graph[START_REF] Merugu | Routing in Space and Time in Networks with Preictable Mobility[END_REF] is another approach to represent DTNs as static graphs that also captures both temporal and resource constraints of the contacts. Even though our discussion is focused on the event-driven graph, the results and algorithms also apply if space-time graph model is adopted.

Contacts can be directed, if two independent wireless channels are used for transmissions in the two directions, or undirected, if the same wireless channel is used for transmissions in both directions and the total capacity can be arbitrarily divided between them. We focus on the first case in this paper.

A node can be source or destination for different packets.

If within M, there are multiple packets that are generated by the same source at the same time, we merge the identical packet generation nodes as one, and sum up the capacity of the corresponding edges.

The residual capacity of an edge is the difference between its capacity and its current flow value, i.e. how much the flow can still be increased on that edge. The residual capacity of a path is defined as the minimum of the residual capacities of all edges in the path.

The piece-wise linear property in this case can be proved in a similar way to the single packet case as shown in[START_REF] Zhang | Study of a bus-based disruption tolerant network: Mobility modeling and impact on routing[END_REF].


Xiaolan Zhang
email: xzhang@fordham.edu.

Giovanni Neglia
email: gio-vanni.neglia@sophia.inria.fr

Jim Kurose
email: kurose@cs.umass.edu

Don Towsley
email: towsley@cs.umass.edu

Haixiang Wang
email: ahawang@fordham.edu.

† Xiaolan Zhang

Benefits of Network Coding for Unicast Application in Disruption Tolerant Networks *

In this paper, we investigate the benefits of applying a form of network coding known as Random Linear Coding (RLC) to unicast application in Disruption Tolerant Networks (DTNs). Under RLC, nodes store and forward random linear combinations of packets as they encounter each other. For the case of a single group of packets originating from the same source and destined for the same destination, we prove a lower bound on the probability that the RLC scheme achieves the minimum time to deliver the group of packets. Although RLC achieves a significant reduction in group delivery delay, it fares worse in terms of average packet delivery delay and network transmissions. When replication control is employed, RLC schemes reduce the group delivery delay without increasing the number of transmissions. In general, the benefit achieved by RLC is more significant under stringent resource (bandwidth and buffer) constraints, limited signaling, highly dynamic networks, and when it is applied to packets from same flow. For more practical settings with multiple continuous flows in the network, we show the importance of deploying RLC schemes with a carefully tuned replication control in order to achieve reduction in average delay.

Introduction

In recent years, wireless communication technologies have been increasingly deployed in environments where there is no communication infrastructure, 1 as evidenced by the many efforts to build and deploy wireless sensor networks for wildlife tracking ( [START_REF] Juang | Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with zebranet[END_REF][START_REF] Haas | A New Networking Model for Biological Applications of Ad Hoc Sensor Networks[END_REF]), underwater sensor networks ( [START_REF] Maffei | Ocean Instrument Internet[END_REF][START_REF] Partan | A Survey of Practical Issues in Underwater Networks[END_REF]), disaster relief team networks, networks for remote areas or for rural areas in developing countries ( [START_REF]First Mile Solutions[END_REF][START_REF] Doria | Providing Connectivity to the Saami Normadic Community[END_REF]), vehicular networks ( [START_REF] Burgess | MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks[END_REF][START_REF] Hull | CarTel: A Distributed Mobile Sensor Computing System[END_REF]) and Pocket-Switched Networks ( [START_REF] Hui | Pocket Switched Networking: Challenges, Feasibility, and Implementation Issues[END_REF]). Without infrastructure support, such networks solely rely on peer-to-peer connectivity between wireless radios to support data communication. Due to limited transmission power, fast node mobility, sparse node density and frequent equipment failures, many such networks exhibit only intermittent connectivity. Disruption Tolerant Network (DTN, or Delay Tolerant Network ) refers to such a network where there is often no contemporaneous path from the source node to the destination node. Endto-end communication in DTNs adopts a so-called "store-carry-forward" paradigm ( [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF]): a node receiving a packet buffers and carries the packet as it moves, passing the packet on to other nodes that it encounters. The packet is delivered to the destination when the destination meets a node carrying the packet. In addition to intermittent connectivity, DTNs often face severe resource constraints. For small mobile nodes carried by animals or human beings, buffer space, transmission bandwidth and power are very limited; for mobile nodes in vehicle based networks, buffer space or power are in general not severely constrained, but transmission bandwidth is still a scarce resource. To address these challenges, a plethora of routing schemes have been proposed for DTNs ([43, 42, 39, 13, 40, 41, 4]): some of these works explore the trade-off between routing performance and resource consumption, whereas others attempt to optimize routing performance under certain resource constraints.

Ahlswede et al. ([3]) demonstrated the benefit of coding at intermediate nodes in terms of approaching the admissible coding rate region for multicast applications, and initiated a new field in information theory, i.e., network coding. Among the many works that followed, a substantial amount of research has studied the benefits of network coding for multicast, broadcast and unicast applications in wireless networks. Although a DTN is a special type of wireless network, due to its distinct characteristics, some benefits of network coding for general wireless networks do not hold. For example, the results obtained in [START_REF] Lun | Network Coding with a Cost Criterion[END_REF][START_REF] Wu | Minimum-Energy Multicast in Mobile Ad hoc Networks using Network Coding[END_REF] for multicast in static wireless networks are not directly applicable to DTNs due to their dynamically changing topology. Also, in DTNs, each node usually has at most one neighboring node at any instance of time, therefore the benefit of network coding in increasing network throughput (by leveraging the broadcast nature of wireless transmission)( [START_REF] Kung | Information Exchange in Wireless Networks with Network Coding and Physical-Layer Broadcast[END_REF][START_REF] Katti | XORs in the air: Practical wireless network coding[END_REF][START_REF] Liu | Bounds on the gain of network coding and broadcasting in wireless networks[END_REF]) is negligible in DTNs.

On the other hand, there are new opportunities for network coding in DTNs. The rapidly changing topology and the lack of infrastructure require DTN routing schemes to be distributed; and the limited connectivity and bandwidth also require DTN routing schemes to be localized, i.e., using only limited knowledge about the local neighborhood. Network coding has been shown to facilitate the design of efficient distributed schemes ( [START_REF] Fragouli | Network Coding: An Instant Primer[END_REF]).

Existing research has studied the application of Random Linear Coding (RLC), a special form of network coding [START_REF] Ho | The Benefits of Coding Over Routing in a Randomized Setting[END_REF], to broadcast and unicast communication in DTNs. In this paper, we use the term RLC scheme to denote a DTN routing scheme that employs RLC, and use the term non-coding scheme to denote a traditional routing scheme. For broadcast applications, Widmer et al. ( [START_REF] Widmer | Network Coding for Efficient Communication in Extreme Networks[END_REF][START_REF] Widmer | Energy-efficient broadcasting in wireless ad-hoc networks[END_REF]) showed that the RLC scheme achieves higher packet delivery rates than the non-coding scheme with the same forwarding overhead. For unicast applications, our earlier work [START_REF] Zhang | On the Benefits of Random Linear Coding for Unicast Applications in Disruption Tolerant Networks[END_REF] first investigated the benefit of RLC through simulation studies. Lin et al. proposed and analyzed a replication control scheme ( [START_REF] Lin | Efficient network coded data transmissions in disruption tolerant networks[END_REF]) for RLC schemes. In [START_REF] Lin | Stochastic Analysis of Network Coding in Epidemic Routing[END_REF], Ordinary Differential Equation (ODE) models are proposed in order to estimate delivery delay and number of transmissions for RLC schemes and non-coding schemes, both for a single group of packets.

This paper presents new contributions that improve our understanding of the benefits of network coding in DTNs unicast application both theoretically and practically. Our main findings are summarized as follows:

• Leveraging event-driven graph model for DTNs ( [START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF]), and existing results on static graphs ( [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF][START_REF] Kleinberg | Algorithm Design[END_REF]), we propose an algorithm to calculate the minimum time to deliver a group of packets, and prove a lower bound on the probability that RLC schemes achieve the minimum delivery time.

• We show that under only bandwidth constraint, the RLC scheme improves group delivery delay, but fares worse in terms of in-order packet delay and average packet delay (and in general, time to deliver a fraction of packets) and generates more transmissions in the network. At the same time, RLC schemes with replication control improve the fundamental trade-off between delay and number of transmissions made.

• We study how resource constraints, and various routing design options affect the benefit of RLC schemes. Especially, RLC provides more significant benefits under substantial buffer and bandwidth constraints, limited control signaling, highly dynamic networks, and when it is applied to packets belonging to the same flow.

• The same results hold when RLC schemes are applied to multiple continuous unicast flows, as long as replication control mechanisms are carefully tuned.

The remainder of this paper is structured as follows. In Sec. 2, we introduce the network model and performance metrics considered in this paper, review the non-coding schemes and the basic of RLC schemes, and discuss the design space of DTN unicast routing schemes. Sec. 3 studies the benefit of the RLC scheme over the non-coding scheme for a group of packets Due to space constraints, the complete description of our algorithm to calculate the minimum group delivery time, the proof of Proposition 3.2 and some details about the simulation experiments are in the companion technical report [START_REF] Zhang | Random Linear Coding for Unicast Applications in Disruption Tolerant Networks[END_REF].

Background

In this section, we first present the network model studied in this paper. We then describe the general approach to unicast routing in DTN with and without RLC, and define the performance metrics we use to study RLC benefits. Last, we provide a discussion about the design space for DTN routing schemes. Table 1 summarizes the notation and the default settings used in simulation experiments.

Network Model and Traffic Setting

We focus on unicast applications where each packet (generated by its source node) is destined to a single destination node. The network consists of a set of N mobile nodes, denoted as V, moving independently in a closed area. Each node is equipped with a wireless radio with a common transmission range so that when two nodes come within transmission range of each other, they can exchange packets. The contact duration is the time duration of this transmission opportunity, while the inter-contact time is the duration of the time interval between two consecutive contacts, i.e. measured from the time that the two nodes go out of the transmission range of each other until the next time they meet again. We refer to the list of node-to-node contacts, sorted in temporal order, as a DTN contact trace, denoted as

L = l 1 , l 2 , l 3 , .... Each contact, l i , is a tuple (t(l i ), s(l i ), r(l i ), b(l i ))
where t(l i ) denotes the time of the contact, s(l i ) and r(l i ) denote respectively the sending and the receiving node of the contact, and b(l i ) denotes the number of packets that can be transmitted during the contact 1 .

As for the buffer constraint, we assume each node can store an unlimited number of packets originated by itself or destined for itself, but can only carry a limited number of packets for other nodes. We represent the buffer constraint as a function, B : V → N where B(u) is the number of relay packets that node u can carry.

(2,10. A contact trace can be represented as a temporal network as originally proposed by Kempe et al. [START_REF] Kempe | Connectivity and Inference Problems for Temporal Networks[END_REF]. The temporal network for contact trace L is a multi-graph T (L) = V, E in which V denotes the set of nodes in the network, and E denotes the set of directed edges. Each contact l ∈ L is represented as an edge, labeled with a pair, (t(l), b(l)), i.e., the time of the contact, and the number of packets that can be exchanged using the contact. For example, Fig. 1(a) illustrates the temporal network model for a contact trace of a DTN with four nodes during the time interval [0,[START_REF] Kempe | Connectivity and Inference Problems for Temporal Networks[END_REF].

Another useful graph representation for a DTN contact trace is the eventdriven graph proposed in [START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF]. For example, Fig. 1(b) shows the event-driven graph corresponding to the contact trace in Fig. 1(a). The eventdriven graph G(L, B) for a contact trace L and buffer constraints B(•) is constructed as follows: for each contact l = (t, u, v, b) ∈ L, two nodes (u, t) and (v, t) are added to the graph G, respectively denoting the sending and receiving event of the contact. A directed inter-node edge (depicted as a horizontal line in Fig. 1(b)), labeled with b, connects node (u, t) to node (v, t), denoting that up to b packets can be transmitted from node u to v at time t. If two consecutive contacts involving node u occur at t 1 and t 2 (> t 1 ), a directed intra-node edge connecting nodes (u, t 1 ) to (u, t 2 ) is added to graph G (depicted as a vertical line in the figure), with a capacity equal to B(u), i.e., the maximum number of relay packets node u can store.

The event-driven graph is a static, i.e., time-independent, graph that represents both temporal constraint of the contacts, and resource (bandwidth and buffer) constraints. [START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF] showed that many problems on DTN routing can be solved by applying classic graph theory algorithms on this static graph. The following proposition is a restatement of Theorem 4 in [START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF]: Proposition 2.1 There is a feasible routing schedule for delivering K packets originated from u immediately before t 1 to node v by time t 2 (t 2 ≥ t 1 ) under contact trace L and buffer constraint B(•) if and only if there is a flow of value K from node (u, t 1 ) to node (v, t 2 ) in the event-driven graph G(L, B).

To see this, we note that the value of a flow on an inter-node edge equals the number of packets sent during the corresponding contact whereas the value of a flow on an intra-node edge corresponds to the number of packets being carried by the node during the corresponding time interval.

In our simulation studies, we assume homogeneous resource constraint, i.e., B(u) = B, for all u ∈ V, and when two nodes encounter each other, b(b ≥ 1) packets can be exchanged in each direction. Most of our simulation results are obtained under the assumption that pair-wise meeting is described by independent Poisson processes with rate β. This simplification speeds up the simulations, and is a good approximation on timescales beyond the average time a node spends to cross the region, when nodes move according to common random mobility models (like random waypoint and random direction) and the network is sparse. This observation was first made by [START_REF] Groenevelt | The Message Delay in Mobile Ad Hoc Networks[END_REF]. Later works ( [START_REF] Karagiannis | Power Law and Exponential Decay of Inter Contact Times between Mobile Devices[END_REF][START_REF] Cai | Crossing over the bounded domain: from exponential to power-law intermeeting time in mobile ad hoc networks[END_REF]) have formally proven that the tail of the Complementary Cumulative Distribution Function (CCDF) of the inter-contact time is actually exponentially bounded for many common random mobility models in a finite region. The characteristic time beyond which the inter-contact time exhibits an exponential behavior has been investigated in [START_REF] Cai | Crossing over the bounded domain: from exponential to power-law intermeeting time in mobile ad hoc networks[END_REF][START_REF] Cai | Toward stochastic anatomy of inter-meeting time distribution under general mobility models[END_REF]. Because of its tractability, the Poisson meeting process has been widely adopted ([12, 30, 40]).

Non-Coding Routing Schemes

Non-coding based unicast routing schemes for DTNs can be classified as single-copy or multi-copy schemes.

Under a single-copy scheme ( [START_REF] Spyropoulos | Efficient Routing in Intermittently Connected Mobile Networks: The Single-copy Case[END_REF]), each packet is forwarded along a single path, and at any point in time, there is a single copy of the packet in the network. Such schemes place minimal demand on the node buffer space, and usually incur a low transmission overhead. But when future contacts are not known in advance, forwarding decisions can later turn out to be wrong and in general lead to suboptimal performance. In such cases, it is often beneficial to use multi-copy schemes to reduce delivery delay and increase the delivery probability.

Under a multi-copy scheme, a packet is copied to other nodes to be simultaneously forwarded along multiple paths to the destination, leading to multiple copies of a packet in the network at a given point in time. For example, epidemic routing proposed by Vahdat and Becker ([43]) floods the whole network in order to deliver a packet. By making use of all transmission opportunities, epidemic routing achieves minimum delivery delay when the network is lightly loaded, but causes severe resource contention under heavier traffic.

RLC based Routing Schemes

In this section, we describe the basic operation of Random Linear Coding (RLC) based DTN routing schemes.

When RLC is applied to packet data networks, the payload of each packet is viewed as a vector of symbols from a finite field F q of size q ( [START_REF] Lidl | Finite Fields[END_REF]). Assuming all packets have the same payload size equal to S bits, each packet can then be viewed as a vector of d = ⌈S/ log 2 (q)⌉ symbols from F q .

A collection of packets that may be linearly coded together is called a generation. Suppose K packets P i , i = 1, 2, ..., K, constitute a generation, we denote by m i ∈ F d q , the symbol vector corresponding to each packet. A linear combination of the K packets is:

x = K i=1 α i m i , α i ∈ F q ,
where addition and multiplication are over F q . The vector of coefficients, α = (α 1 , ..., α K ) is called the encoding vector, and the resulting linear combination, x, is called an encoded packet. We say that two or more encoded packets are linearly independent if their encoding vectors are linearly independent. Each original packet, m i , i = 1, 2, ...K, is a special combination with coefficients α i = 1, and α j = 0, ∀j = i.

Under RLC schemes, network nodes store and forward encoded packets, together with their encoding vectors. For a generation of size K, the coef-ficients take up K symbols; while the payload is d = ⌈S/ log 2 (q)⌉ symbols. This leads to a relative overhead, i.e., the ratio of the size of the encoding coefficients and the payload, of K/(⌈S/ log 2 (q)⌉) ≈ K log 2 (q)/S.

If the set of encoded packets carried by a node contains at most r linearly independent encoded packets x 1 , ..., x r , we say that the rank of the node is r. We refer to the r × K matrix (denoted as A) formed by the encoding vectors of x 1 , ..., x r as the node's encoding matrix. Essentially, the node stores r independent linear equations with the K original packets as the unknown variables, i.e., AM = X, where M = (m 1 , m 2 , ..., m K ) T is the K × d matrix of the K original packets, and X = (x 1 , x 2 , ...x r ) T is the r × d matrix of the r encoded packets. When a node (e.g., the destination) reaches rank K (i.e., full rank ), it can decode the original K packets through matrix inversion, solving AM = X for M = A -1 X using standard Gaussian elimination algorithm2 .

We illustrate data forwarding under RLC schemes using the transmission from node u to node v as an example. Node u generates a random linear combination of the encoded packets in its buffer x 1 , ..., x r : x new = r j=1 β j x j , where the coefficients β 1 , ...β r are chosen uniformly at random from F q . Clearly, x new is also a linear combination of the K original packets. This new combination, along with the coefficients with respect to the original packets, is forwarded to node v. If among x 1 , ..., x r , there is at least one combination that cannot be linearly expressed by the combinations stored in node v, node u has useful (i.e., innovative) information for node v, and x new is useful to node v (i.e., increases the rank of node v) with probability greater than or equal to 1 -1/q (Lemma 2.1 in [9])3 .

Performance Metrics

We assume that each message generated by the application is segmented into a group of packets in order to take advantage of short contacts ( [START_REF] Pitkanen | Message Fragmentation in Opportunistic DTNs[END_REF]). We denote the group of packets belonging to a message as P i , i = 1, 2, ..., K, and the delivery delay of packet P i as D i for i = 1, 2, ..., K. If we assume that the destination can only process the message after all packets in the message are delivered, then an important metric is the group delivery delay, D g , defined as the time from the generation of the message, i.e. of the group of packets, to the delivery of the entire group to the destination, and we have D g = max 1≤i≤K D i . Depending on the specific application, other metrics might be more meaningful. For example, if the application can process each packet individually upon its delivery, then average packet delivery delay-D a = K i=1 D i /K-should be considered 4 . Finally, if packets must be processed by the destination in order, i.e., if P i can be processed only after all packets P j , 1 ≤ j ≤ i have been delivered, then the average in-order packet delivery delay should be considered, where the in-order packet delivery delay for packet P i is defined as D ′ i = max 1≤j≤i D i , for i = 1, 2, ..., K. For applications that generate small messages, segmenting the message into even smaller packets would lead to a large relative overhead (for packet headers and encoding vectors). In such applications, RLC can be applied to a group of packets whose generation times are close to each other.

In our study, we have assumed that all the information transmitted has to be delivered, and therefore we consider delivery delay as the most important performance metric. There are network scenarios and applications where packet losses may be tolerated or have to be tolerated, so that a more relevant performance metric may be the percentage of packet delivered by a given deadline. We discuss these cases in Sec. 6.

As a measure of resources consumed (bandwidth and transmission power) in the network, we consider the total number of transmissions made within the network for the group. There exists an inherent trade-off between the delivery delay and the number of transmissions made, which is further studied in Sec. 3.3.

Design Space

We now discuss various design options for DTN routing schemes, all of which, but for generation management, are applicable to both non-coding and RLC schemes 5 .

Control Signaling. Nodes in the DTNs periodically broadcast and listen for beacon messages in order to discover their neighbors, and exchange information about the packets/encoded-packets carried by each other. Such control signaling is useful for nodes to decide whether to transmit and what information to transmit. We consider the following different control signaling.

• Normal Signaling: signaling is limited to periodic beacon messages in order to discover neighbors. A node only transmits packets when it detects at least one neighbor.

• Full Signaling: after two nodes discover each other via beaconing, they exchange information about what they carry. Under the non-coding scheme, they exchange the sequence numbers of the packets they carry.

The node then transmits only packets that the other does not carry. Under the RLC scheme, the nodes exchange the encoding vectors, so that each node only transmits if it has useful information for the other node.

Simulation results reported in the paper are for full signaling case, unless otherwise specified as in Sec. 3.4.2.

Transmission Scheduling and Buffer Management. Routing schemes for resource constrained DTNs need to deal with resource contention through transmission scheduling and buffer management ( [START_REF] Balasubramanian | DTN Routing as a Resource Allocation Problem[END_REF][START_REF] Krifa | Optimal buffer management policies for delay tolerant networks[END_REF]). When a node encounters another node, the scheduler decides, among all candidate packets or generations in its buffer, which packets or generations to transmit to the other node. When a node with a full buffer receives a new (encoded) packet, it decides whether and how to make space for the new packet based on its buffer management policy. Existing works ([4, 26, 27]) have proposed to estimate the utility of each packet, and select the packets to transmit or drop based on packet utility in order to optimize some system performance metric. These schemes typically require nodes to estimate and exchange additional control information about node mobility or packet propagation status for packet utility calculation.

In our studies of the benefit of RLC, we adopt the following simple transmission scheduling for the non-coding scheme and the RLC scheme 6 . When there are multiple unicast flows in the network, during an encounter, a node gives higher transmission priorities to packets/generations destined to the receiver node; furthermore, among such packets/generations, those originated from the node itself are served first. Under the non-coding scheme, a node selects uniformly at random a packet among candidate relay packets with the same priority, and perform a round robin scheduling among source packets it carries 7 . For the RLC scheme, during an encounter, a node selects uniformly at random a generation to transmit from all candidate generations with the same priority. Scheduling among packets from the same generation is performed via RLC operation, i.e., a node transmits a random linear combination of the encoded-packets it carries to the other node.

As for buffer management, we consider the drophead scheme for noncoding schemes: when buffer is full, the node drops the relay packet that has resided in the buffer the longest. For the RLC scheme, when a node with a full buffer receives a new encoded packet, it chooses a generation from its buffer that has the highest rank (ties are broken randomly). If the newly received packet belongs to the selected generation, one existing encoded packet of the generation is replaced by its random linear combination with the newly received packet. Otherwise, the node randomly selects two encoded packets from the chosen generation, and replaces them with their random linear combination.

Recovery Scheme. Multi-copy DTN routing schemes often employ recovery schemes to save resource [START_REF] Haas | A New Networking Model for Biological Applications of Ad Hoc Sensor Networks[END_REF][START_REF] Zhang | Performance Modeling of Epidemic Routing[END_REF]. For example, under the VACCINE recovery, an anti-packet (delivery acknowledgment information) is generated by the destination upon packet delivery, and it is then propagated in the entire network, in the same fashion that data packets propagate under epidemic routing, to delete obsolete copies of the packet. We focus on VAC-CINE recovery as it leads to the most significant resource savings among the different recovery schemes. We extend VACCINE recovery scheme to work with RLC so that when a generation of packets is first delivered to its destination, the destination generates an anti-generation which is then propagated in the network to delete remaining copies of packets or encoded packets belonging to the generation.

Replication Control. In resource constrained DTNs where nodes have limited energy or finite transmission bandwidth, or both, it is beneficial to control the total number of times that a packet (or a generation) is transmitted in the network, through so called replication control mechanisms. Replication control mechanisms trade-off delivery delay for resource consumption. Some of these mechanisms limit the number of transmissions via setting a maximum hop count, or a TTL timer for packet copies, while others such as spray-and-wait directly limit the number of transmissions.

Under the binary spray-and-wait ( [START_REF] Spyropoulos | Spray and wait: an efficient routing scheme for intermittently connected mobile networks[END_REF][START_REF] Spyropoulos | Efficient Routing in Intermittently Connected Mobile Networks: The Multi-copy Case[END_REF]), the source node assigns a number of tokens, denoted as C, to each source packet it generates, which specifies the maximum number of transmissions that can be made for the packet in the network. When a node carrying a packet with token value c (c ≥ 2) meets another node that does not carry a copy of the packet, the packet is copied to the latter node and the c tokens are equally split between the two copies of the packet, i.e., the former copy keeps ⌈c/2⌉ tokens and the new copy is assigned ⌊c/2⌋ tokens. A node carrying a packet with token value c ≤ 1 can only deliver the packet to the destination. In this way, the total number of transmissions made for the packet in the whole network is upper-bounded by C, though the actual number of copies being made is often smaller when a recovery scheme is employed. In Sec. 3.3, we extend the binary spray-and-wait to be used in conjunction with RLC.

Generation Management. An RLC scheme needs to address the question of how many and which packets form a generation. Packets cannot be arbitrarily coded together. First, as we have observed, the overhead of trans-mitting and storing encoding coefficients grows with the generation size, and so does the complexity of encoding and decoding operations. Second, for unicast applications, when K packets destined to K different nodes are coded together, each of the K destinations has to receive K encoded packets in order to decode the one packet destined to it. We discuss in more depth the impact of generation management in Sec. 4.1.

Single Source Case

In this section, we focus on the case where a group of packets, from a single unicast source, propagate in a DTN where bandwidth and buffer are constrained. We first present an algorithm to calculate the minimum group delivery time under a contact trace and buffer constraints, provide intuition about why RLC schemes without replication control achieve this minimum time with higher probability than non-coding schemes, and present a lower bound for this probability (Sec. 3.1). We then discuss other performance metrics (Sec. 3.2), and demonstrate that RLC schemes improve the delay-per-transmission in comparison to non-coding schemes when replication control is employed (Sec. 3.3). Finally, we discuss how bandwidth and buffer constraints, different control signaling, realistic mobility traces and node churn affect the benefits of RLC schemes (Sec. 3.4).

Probability to Achieve Minimum Group Delivery Time

We use the 4-tuple (s, d, t 0 , K) to denote a group of K unicast packets generated by source node s at time t 0 , all of which destined for the same destination d. For a 4-tuple (s, d, t 0 , K) that can be delivered to the destination under the contact trace L and buffer constraints B(•), there is a minimum group delivery time by which all of the K packets can be delivered to the destination. This time is in general achievable only by an oracle scheme with knowledge of all future contacts, and provides a lower bound for the group delivery time achieved by any practical routing scheme. We first propose an algorithm for calculating the minimum group delivery time.

The algorithm

We first explain how to determine whether the group of K packets can be delivered under the contact trace L and buffer constraints B(•). To address this issue, we first build the event-driven graph G(L, B), and then enlarge this graph by adding two nodes: node (s, t 0 ) that is connected by an intranode edge with capacity K to the node (s, t 1 ), where t 1 is the time of the first contact after t 0 involving node s, and a special node (d) to which all nodes involving node d are connected. These edges have a capacity of K, as up to K packets can be transmitted from node (d, t) (with t > t 0 ) to The newly added edges are drawn with dashed lines, and the updated intra-node edge capacity is highlighted using bold font. The maximum flow from (1, 0) to ( 4) is 2, achieved by the following two paths (1, 0), (1, 1.2), (2, 1.2), (2, 7), (2, 10.2), (4, 10.2), (4), and (1, 0), (1, 1.2), (1, 3.5), (3, 3.5), [START_REF] Ahlswede | Network information flow[END_REF][START_REF] Katti | XORs in the air: Practical wireless network coding[END_REF], [START_REF] Balasubramanian | DTN Routing as a Resource Allocation Problem[END_REF][START_REF] Katti | XORs in the air: Practical wireless network coding[END_REF], ( 4).

(d). We also change the capacity of all intra-node edges for the source node s and the destination node d to K, as we assume nodes have enough buffer to store source packets or packets destined for them. We denote this augmented event-driven graph as G ′ (L, B, (s, d, t 0 , K)). For example, Fig. 2 plots the augmented event-driven graph for the group of packets (1, 4, 0, 2) under the DTN trace depicted in Fig. 1, with B(u) = 2, ∀u ∈ V. Based on Proposition 2.1, the group of packets (s, d, t 0 , K) can be delivered under contact trace L and buffer constraints B(•) if and only if there is a flow of value at least K from (s, t 0 ) to (d) in G ′ (L, B, (s, d, t 0 , K)). We therefore have the following proposition: Proposition 3.1 To determine the minimum group delivery time for the 4tuple (s, d, t 0 , K) under a contact trace L and buffer constraints B(•), it suffices to find L min , the shortest left subsequence of L such that the augmented event-driven graph G ′ (L min , B, (s, d, t 0 , K)) can support a flow of value K from (s, t 0 ) to (d). The time of the last contact in L min is the minimum group delivery time.

Algorithm MIN DELIVERY TIME (Alg.1) intertwines the steps of searching for L min with the iterations of the Ford-Fulkerson algorithm for the maximum-flow problem ( [START_REF] Kleinberg | Algorithm Design[END_REF]). A complete description is provided in [START_REF] Zhang | Random Linear Coding for Unicast Applications in Disruption Tolerant Networks[END_REF]. Starting with an empty augmented event-driven graph G f = G ′ (∅, B, (s, d, t 0 , K)) = {(s, t 0 ), d}, ∅ , the algorithm iterates the expand graph phase and the find max-flow phase until the value of the flow reaches K or all contacts in L have been processed (in this case the K packets cannot be delivered under the trace).

In the expand graph phase, the graph G f is expanded by considering events from L according to their time order, until FIND PATH (G f , (s, t 0 ), (d)) finds a new path with a non-zero residual capacity8 from node (s, t 0 ) to node (d). Here GROW(G f , B, l) expands G f by processing contact l ∈ L, following the procedure described in Sec. 2.1.

Once a path is found, the algorithm enters the find max-flow phase where the flow is augmented until the max-flow from node (s, t 0 ) to (d) in G f is determined. While the Ford-Fulkerson algorithm [START_REF] Kleinberg | Algorithm Design[END_REF] used here is not the most efficient max-flow algorithm, it allows us to incrementally augment the flow instead of starting the maximum flow calculation from scratch every time the graph is expanded. The procedure UPDATE RESIDUAL GRAPH(G f ,P ) implements the following two steps of Ford-Fulkerson algorithm: augmenting the flow along path P and updating the residual graph. The returning value b is the increment of the flow value due to path P .

If a flow of value at least K is determined, Alg.1 returns the time of the last contact that has been considered. Otherwise, it returns a negative value -f (the sign denotes the failure to deliver the whole group of packets, and f yields the number of packets that can be delivered). Let L ′ be the subsequence of the contact trace L considered up to termination, the computational complexity of Alg. 1 is O(K|L ′ |).

Alg.1 can be extended to return the set of paths that supports the flow of value K in the event-driven graph. The set of paths corresponds to a specific DTN routing schedule that achieves the minimum group delivery time. For example, the two paths (1, 0), (1, 1.2), (2, 1.2), (2, 7), (2, 10.2), (4, 10.2), ( 4) and (1, 0), (1, 1.2), (1, 3.5), (3, 3.5), [START_REF] Ahlswede | Network information flow[END_REF][START_REF] Katti | XORs in the air: Practical wireless network coding[END_REF], [START_REF] Balasubramanian | DTN Routing as a Resource Allocation Problem[END_REF][START_REF] Katti | XORs in the air: Practical wireless network coding[END_REF], (4) in Fig. 2 support a flow of value 2 from (1, 0) to node (4), and correspond to a set of two paths that achieves the minimum group delivery time for the group of packets (1, 4, 0, 2).

Probability to achieve minimum group delivery time

In practical settings, network nodes, without prior knowledge about contacts in the network, might choose "wrong" packet(s) (or encoded packet(s) for RLC schemes) to forward during a contact or to delete when the buffer is full. As a result, the destination might receive redundant information through the K forwarding paths that achieve the minimum group delivery time, and more time is needed to deliver the group of packets. Compared to non-coding schemes, RLC schemes reduce the probability of making wrong choices, due to the larger set of possible useful encoded packets: at a given time, the number of linear combinations useful for the destination is much greater than the number of useful packets. For example, under a randomized non-coding scheme, if a relay node carries r ≤ K packets, one of which has already Algorithm 1 MIN DELIVERY TIME (L, B, s, d, t 0 , K), find minimum group delivery time for the group of packets, (s, d, t 0 , K), under contact trace L and buffer constraints B(•)

1: Input: L, B, s, d, t 0 , K 2: L r = L, f = 0, G f = {(s, t 0 ), (d)}, ∅ 3: while f < K and L r = ∅ do 4:
// Expand Graph Phase

G ′ f =GROW(G f , l, B), G f ← G ′ f 10:
until r(l) = d // Until the node d is the receiving node of contact l 11:

P =FIND PATH(G f , (s, t 0 ), (d))

12:

until P = null 13:

// Find Max-Flow Phase 14:

while P = null and f < K do 15:

(G ′ f , b)=UPDATE RESIDUAL GRAPH(G f , P ) 16: G f ← G ′ f , f ← f + b 17: P =FIND PATH(G f , (s, t 0 ), (d)) 18:
end while 19: end while 20: if f ≥ K then return -f // return the negative of f 24: end if been delivered to the destination, the probability that this relay chooses to forward the useless packet is 1/r. Whereas under the RLC scheme, if the rank of a relay node is r, and the destination carries one combination that is linearly dependent from the r encoded packets carried by this relay node, the probability that the combination forwarded by the relay node is useless for the destination is 1/q r-1 where q is the size of the finite field. In general, r > 2, 1/q r-1 << 1/r (e.g., q = 2 8 is a commonly used finite field size in RLC).

Under no replication control, the RLC scheme makes use of all contacts to propagate the generation, including those contacts along the set of K forwarding paths that achieves the minimum group delivery time. We denote by η the number of transmission scheduling and buffer management decisions that network nodes make under the RLC scheme along this set of forwarding paths. This number affects the probability that the RLC scheme achieves the minimum group delivery time. Obviously, η is upper bounded by the total hop count (including intra-node and inter-node edges) of the set of paths, denoted as H total . The actual value of η depends on the specific contact trace, buffer constraints and packet group.

For the example in Fig. 2, we have η = 3 as network nodes need to make three transmission scheduling decisions, respectively during the contacts (1, 2, 1.2), (1, 3, 3.5) and (2, 4, 10.2) 9 , and zero buffer management decision. The total number of hops of this set of paths is H total = 9 > 3 = η.

We note that the RLC DTN routing scheme corresponds to a RLC routing scheme on the corresponding event-driven graph, which is a static graph. Theorem 3 in [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF] applies to RLC on static graphs and provides a lower bound on the probability (in terms of finite field size, number of edges with random coefficients, and number of receivers) for an RLC scheme to support a set of feasible multicast flows. Using this result we prove the following proposition (see [START_REF] Zhang | Random Linear Coding for Unicast Applications in Disruption Tolerant Networks[END_REF] for details): Proposition 3.2 Consider a group of packets (s, d, t 0 , K) propagating under a contact trace L with buffer constraint B(•), and a set of K forwarding paths that achieves the minimum group delivery time. Let η be the number of scheduling and buffer management decisions that DTN nodes perform under the RLC scheme along this set of paths. The RLC scheme achieves the minimum group delivery time with probability greater than or equal to (1 -1/q) η . by the RLC and the non-coding scheme over 100 different simulation runs for the cases with and without buffer constraints (B = ∞, B = 1). All the simulation experiments in this paper have been carried as follows: 1) unless otherwise specified, the default parameter settings in Table 1 have been used, 2) at each simulation run the random number generator (used for generating the contact trace and RLC random coefficients, and for random transmission scheduling and buffer management) is initialized with a different seed, 3) the same set of contact traces is considered for all the schemes. Fig. 3(a) shows that the CDFs of the RLC scheme and of the minimum group delivery delay for both cases almost overlap. A closer inspection shows that the RLC scheme achieves the minimum group delivery delay in 98 out of 100 runs for the B = ∞ case and in 95 out of 100 runs for the B = 1 case. In contrast, the delivery delay under the non-coding scheme is larger, especially when the buffer is limited.

Other Performance Metrics

We now compare the RLC scheme and non-coding scheme in terms of other delay metrics and the total number of transmissions made in the network, using the same set of simulations as presented in the last section, focusing on the case without buffer constraint. We first consider the average packet delay and average in-order packet delay. Fig. 3(b) plots the CDFs of different delay metrics achieved by the RLC scheme and the non-coding scheme from the 100 different simulation runs (with B = ∞). There are four almost overlapping curves. They are the CDFs of the minimum group delay and the three different delay metrics achieved by the RLC scheme. Under the RLC scheme, the average delay and the average in-order delay are only slightly smaller than the group delivery delay. In this setting, the non-coding scheme fares worse in terms of group delivery delay and of in-order delivery delay, but performs better in terms of average packet delay. However, the RLC scheme performs better in terms of all the 3 metrics if B = 1 (the figure is omitted due to space constraint).

We now briefly consider the delay to deliver a certain fraction of the packets. Fig. 3(c) plots the CDFs of the group delivery delay, and of the time for the destination to receive 10% and 90% of the packets. For the RLC scheme the 3 curves are almost identical, so that we plot a single curve. In this particular setting, the destination can receive later the first packet under the RLC scheme than under the non-coding scheme, but it can decode faster the first 9 packets. Therefore if the application requires a target delivery probability higher than 90%, the RLC scheme outperforms the non-coding scheme. We discuss more this issue in Section 6.

RLC schemes achieve faster information propagation at the price of a greater number of transmissions and a larger buffer occupancy. For example, Fig. 4(a) plots the total numbers of packet copies (for the non-coding scheme) or combinations (for the RLC scheme) in the network as a function of time for one simulation run (the group of packet is generated at time t = 0). Under the RLC scheme, the probability that two nodes that meet each other have useful information to exchange is higher, leading to a sharper increase in the total number of copies/combinations in the network. Furthermore, under the RLC scheme, the recovery process starts only when the whole generation is delivered, whereas under the non-coding scheme, the recovery process for an individual packet starts immediately when the packet is delivered.

Delay vs. Number of Transmissions Trade-off

For the RLC scheme to be beneficial in resource constrained DTNs, the RLC scheme needs to improve the delay performance without incurring higher transmissions overhead than the non-coding scheme.

We propose the token-based RLC scheme which extends the binary sprayand-wait. A certain number of tokens (denoted as C g ) is assigned to each generation to limit the total number of combinations that can be transmitted for the generation in the network. The operation of RLC schemes is extended with the following consideration on tokens 10 . When two nondestination nodes meet, they redistribute their tokens in proportion to their ranks (see [START_REF] Zhang | Random Linear Coding for Unicast Applications in Disruption Tolerant Networks[END_REF] for more details). Then each of the two nodes transmits a random linear combination to the other if it has useful information and if it has more than one token. After each transmission, the sending node reduce its number of tokens by one. The two procedures (token reallocation and transmission of one combination) are repeated until the contact terminates. This way, the total number of transmissions made to non-destination nodes is bounded by C g . When a node meets the destination, it transmits as many combinations as it can, independently from its number of tokens. Under full signaling the total number of transmissions to the destination (for the destination to reach full rank) is K with probability greater than or equal to (1 -1/q) K-1 (Sec. 2.3). In summary, this scheme limits the total number of transmissions in the network to C g + K with high probability. The actual number is smaller when a recovery scheme is employed. A different replication control scheme, called E-NCP, was proposed in [START_REF] Lin | Efficient network coded data transmissions in disruption tolerant networks[END_REF]. For a group of K packets, the source disseminates K ′ (slightly larger than K) random linear combinations (which are referred to as pseudo source packets) to the first K ′ relays that it encounters. Each of the K ′ relays then uses binary spray-and-wait to limit the total number of transmissions made for the pseudo source packet it carries. Different pseudo source packets are randomly and linearly combined at relay nodes, as under regular RLC scheme.

We compare the group delivery delay versus transmission number tradeoff achieved by the non-coding scheme (with binary spray-and-wait applied to each of the K packets), the token-based RLC scheme, and the E-NCP scheme under varying token number. Fig. 4.(b) and (c) plots the average group delivery delay versus the average number of transmissions (together with the 95% confidence intervals from 100 simulation runs) trade-off achieved by the RLC scheme and non-coding scheme under different token numbers, respectively for the cases without buffer constraints and with a buffer constraint B = 2. We observe that, with a similar number of transmissions, the two RLC schemes achieve smaller group delivery delay than the non-coding scheme. Token-based RLC scheme outperforms E-NCP, especially under small number of transmissions. Under limited relay buffer, the RLC schemes improve the trade-off between group delivery delay and number of transmissions significantly.

Discussion of RLC benefits

In this section, we study how resource constraints, signaling level, mobility patterns, and the fraction of on-and-off nodes affect the benefits of RLC schemes.

Impact of Different Bandwidth and Buffer Constraints

We first consider the impact of varying bandwidth constraint while fixing the buffer constraint B = K (i.e., no buffer constraint). We observe that as the network bandwidth becomes less constrained, the benefit of RLC diminishes and disappears when the number of packets that can be exchanged during each contact, b, equals the group size K. In this case, the K packets propagate independently without competing for bandwidth, and the group delivery delay coincides with the epidemic routing delay under no resource constraints ( [START_REF] Zhang | Performance Modeling of Epidemic Routing[END_REF]). For example, Fig. 5(a) plots the average group delivery delay and its 95% confidence interval (based on 100 different simulation runs) under varying bandwidth constraints, for a group of K = 10 packets from the same unicast flow.

We have observed much more significant RLC benefit under buffer constraint (Fig. 3(a)), and now we consider the benefit of RLC schemes under varying buffer constraint. Fig. 5(b) plots the average group delivery delay (and the 95% confidence interval) for a group of K = 10 packets achieved by the RLC scheme and the non-coding scheme under varying node buffer sizes, B. We observe that as buffer space becomes more constrained, performance under the RLC scheme degrades only slightly, in sharp contrast to the non-coding scheme. As different packets are mixed randomly by nodes under the RLC scheme during transmission or buffer management decision, the RLC scheme allows a more uniform distribution of different packets in the network. For the non-coding scheme, the more copies a packet has in the network, the more the packet is copied to other nodes and evicts copies of other packets when buffer is full. This results in an uneven propagation of different packets: some packets spread quickly to a large number of nodes, while others spread much more slowly. Hence, it takes much longer to deliver the "slowest" packet and therefore the whole group of packets.

Impact of Control Signaling

Simulation results presented so far are for the full signaling case, where two encountering nodes exchange information about what they carry, and decide whether and what to transmit to the other node based on such information. Full signaling incurs a higher transmission and computational overhead for the RLC scheme than for the non-coding scheme, as each node needs to exchange the encoding matrix (in comparison to packet sequence numbers), and calculate whether it has useful information for the other node.

We now consider normal signaling, where two nodes encountering each other do not exchange information about what they carry. For the noncoding scheme, a node randomly chooses a packet from the set of packets it carries, and forwards it to the other node; for the RLC scheme, a node always generates and transmits a random linear combination to the other node. Fig. 5(c) plots the group delivery delay versus the number of transmissions trade-offs achieved by the non-coding and the RLC scheme with full signaling and normal signaling under varying token numbers. We observe that the non-coding scheme performs significantly worse under normal signaling, whereas the performance of the RLC scheme is almost not affected by the lack of information.

Impact of Real Mobility Behavior

To study the impact of real mobility, we compare the performance of the RLC scheme and non-coding scheme using contact traces collected from the UMass DieselNet [START_REF] Burgess | MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks[END_REF] testbed in the spring semester of year 2006. The DieselNet contact traces correspond to a challenging scenario where most of the packets cannot be delivered on a time horizon of 12 hours. The RLC scheme increases the probability to deliver a group of packets from the 24% achieved by the non-coding scheme to 31%. Our experiments are described in [START_REF] Zhang | Random Linear Coding for Unicast Applications in Disruption Tolerant Networks[END_REF] in details.

Impact of Nodes Churn

We now briefly consider a more dynamic setting where some nodes alternate between an On state where they participate in routing and an Off state where they turn off their radios, but keep their buffered packets. We call such nodes as On-Off nodes. The other nodes (including the source and the destination) are always active. Fig. 6 plots the average group delivery delay under different number of On-Off nodes. For On-Off nodes, the duration of the On periods and of the Off periods is uniformly distributed respectively in [0, 50] and in [0, 100]. When the fraction of On-Off nodes increases, the relative benefit of RLC becomes more significant both in absolute and relative values. The increased randomness of the RLC scheme make it more robust to (temporary) loss of information due to nodes being turned off.

Multiple Unicast Flows

We have shown that RLC schemes achieve faster delivery of a group of packets from the same unicast flow than non-coding schemes, at the cost of a larger number of network transmissions. Furthermore, when replication control is employed, RLC schemes improve the trade-off between delivery delay and transmission number. The next question to ask is whether RLC schemes provide any benefit when multiple unicast flows are present in the network. The presence of multiple flows adds a new dimension to generation management, in fact one can limit coding to packets belonging to the same flow (intra-flow coding), or allow coding packets belonging to different flows (inter-flow coding), where nodes combine packets from different sources but destined for the same destination, or even combine packets regardless of their source and destination. Next, we first examine the benefits achieved by RLC under inter-flow coding for the case where there is a single generation in the network, and then focus on studying intra-flow coding in a network with multiple unicast flows.

Inter-Flow Coding

The focus of Sec. 3 is the benefit of RLC when applied to a group of packets originating from a single source and destined for a single destination, i.e., the Single-Source Single-Destination (SS SD ) case. Now we investigate the benefit of applying RLC to: i) a group of K packets originating from K different sources and destined for the same destination, i.e., Multiple-Sources Single-Destination (MS SD ) case, and ii) a group of K packets originating from K different sources and destined for K different destinations, i.e., Multiple-Sources Multiple-Destinations For the MS SD case, Alg. 1 can be extended to calculate the minimum group delivery time (see [START_REF] Zhang | Random Linear Coding for Unicast Applications in Disruption Tolerant Networks[END_REF] for details). We perform simulations to compare the group delivery delay achieved by the RLC scheme and the non-coding scheme against this baseline, and plot the CDFs (from 100 different simulation runs) of the minimum delivery delay and of the group delivery delay under the non-coding and RLC scheme in Fig. 7(a). We note that the RLC scheme achieves smaller group delivery delays than the non-coding scheme, and the delays are close to the minimum possible.

The token scheme described above can be applied also to MS SD and MS MD cases by assigning a per-packet token number C to each of the K packets at its respective source upon packet generation. The subsequent operations are the same as the SS SD case: a node is always allowed to transmit to the destination (for the MS SD case) or one of the K destination nodes (for the MS MD case), even when its token number is zero. Similar to the SS SD case, the total number of transmissions made in the network is bounded by CK + K under the MS SD case, and by CK + K 2 under the MS MD case with high probability.

Simulation studies show that for the MS SD case, the RLC scheme and the non-coding scheme achieve almost identical trade-off curves when buffers are not constrained. However, when the buffer is constrained, the RLC scheme improves the trade-off, as illustrated in Fig. 7(b).

For the MS MD case, we compare the average packet delivery delay11 versus the total number of transmissions made trade-off achieved by the non-coding and the RLC scheme. Fig. 7(c) plots the results for the cases i) when only bandwidth is constrained (b = 1), and ii) when both band-width and buffer are constrained (b = 1, B = 1). We observe that the RLC scheme performs worse than the non-coding scheme in the former case. This is reasonable as the RLC scheme forces each destination to receive K independent combinations in order to decode the one single packet destined for it. When buffers are also constrained, we observe that with a small total number of transmissions, the RLC scheme performs worse than the noncoding scheme; however, when a relatively larger number of transmissions is allowed, the RLC scheme achieves better trade-off than the non-coding scheme.

Given that RLC is most advantageous when applied to packets from the same flow, we focus on intra-flow coding in the case of multiple continuous flows in the next section.

Multiple Continuous Flows with Intra-flow coding

We now assume there are N unicast flows in the network, and each source independently generates groups of K = 10 packets according to a Poisson process with rate λ. RLC is applied to packets belonging to the same group.

We perform simulation studies for a network with N = 101 nodes, assuming bandwidth constraint of b = 1 and no buffer constraint, to compare the delivery delay performance achieved by the RLC scheme and the noncoding scheme (without replication control) under varying traffic rate λ. We observe that the RLC scheme without replication control achieves reduction in group delivery delay at a relatively low traffic rate; but performs worse than the non-coding scheme at a relatively higher traffic rate, as shown in Fig. 8(a), which plots the CDFs of group delivery delay (for all groups in the network) in steady state under the RLC scheme and the non-coding scheme for λ = 0.45 × 10 -3 .

We can explain this result as follows. First, at a relatively high traffic rate, there is a large number of different packets in the network. it is therefore more likely that under the non-coding scheme, two nodes can exchange useful information when they meet. This means that the RLC scheme achieves a smaller relative benefit. Secondly, RLC schemes incur a larger number of transmissions for each generation, and when the group arrival rate is high, contention for bandwidth under RLC schemes is greater than under non-coding schemes and some of the flows can be severely penalized 12 .

To alleviate resource contention, we resort to replication control. For both the RLC scheme and the non-coding scheme, we vary the per-packet token number, C, between 20 and 100. Fig. 8(b) plots the average group delivery delay under different per-packet token numbers at a low rate λ = 0.2 × 10 -3 , a medium rate λ = 0.45 × 10 -3 , and a high rate λ = 0.6 × 10 -3 . Under the medium and high traffic rates, the RLC scheme achieves a smaller average group delivery delay only when the token number is carefully tuned. For example, under λ = 0.45 × 10 -3 case, the optimal token number value is between 40 and 50: if the token number is too large, severe contention leads to degraded performance; if it is too small, some contacts are not exploited because all the tokens have been consumed. For the non-coding scheme, under a token number smaller than 100, contention is not significant and a smaller token number leads to a larger average group delay. We do observe that under a higher traffic rate, the non-coding scheme also benefits from replication control. How to configure replication control schemes for a given network setting is an open problem ( [START_REF] Zhang | Impact of Source Counter on Routing Performance in Resource Constrained DTNs[END_REF]), and beyond the scope of this paper.

As with the single generation case, the RLC benefit under multiple flow case is more significant when buffer is also constrained. We repeat the simulation as shown in Fig. 8(b), introducing buffer constraint of B = 3. The result as plotted in Fig. 8(c) again shows that RLC is more beneficial when both buffer and bandwidth are constrained. In this particular setting, RLC reduces the average group delivery delay by more than 20% for token values ranging from 20 to 100.

Related Work

Several works ( [START_REF] Jain | Using Redundancy to Cope with Failures in a Delay Tolerant Network[END_REF][START_REF] Wang | Erasure-coding based routing for opportunistic networks[END_REF]) have applied erasure coding ( [START_REF] Reed | Polynomial Codes over Certain Finite Fields[END_REF][START_REF] Luby | LT codes[END_REF]) to DTNs, where the source encodes a message into a large number of blocks, such that as long as a minimum fraction of the coded blocks is received, the message can be decoded. For DTNs where there is prior knowledge about paths and their loss behavior, Jain et al. ( [START_REF] Jain | Using Redundancy to Cope with Failures in a Delay Tolerant Network[END_REF]) studied how to allocate the coded blocks to the multiple lossy paths in order to maximize the message delivery probability. To reduce the variance of delivery delay in DTNs with unpredictable mobility, Wang et al. ([44]) proposed to encode each message into a large number of coded blocks which are then transmitted to a large number of relays helping to deliver the coded blocks to the destination. We note that network coding is a generalization of erasure coding, and the benefits of erasure coding scheme can also be achieved by RLC schemes.

While Widmer et al. ([45,[START_REF] Widmer | Energy-efficient broadcasting in wireless ad-hoc networks[END_REF]) studied the benefit of RLC for broadcast applications in DTNs, we study unicast applications for which replication control and recovery schemes are introduced. Our finding that under normal signaling, the relative benefit of RLC is much more significant than that under full signaling is in line with the similar finding about broadcast application in [START_REF] Widmer | Network Coding for Efficient Communication in Extreme Networks[END_REF].

Using the connection between E-NCP and the low-density distributed erasure codes ( [START_REF] Dimakis | Decentralized Erasure Codes for Distributed Networked Storage[END_REF]), [START_REF] Lin | Efficient network coded data transmissions in disruption tolerant networks[END_REF] proved that in order for the destination to decode all K packets with any K encoded packets with high probability, it suffices to set the per-packet token limit in E-NCP to Θ(log K). In contrast, we compare different replication control schemes in terms of the fundamental performance trade-off between delivery delay and number of transmissions.

Lin et al. ( [START_REF] Lin | Stochastic Analysis of Network Coding in Epidemic Routing[END_REF]) developed ODE models to analyze the group delivery delay for a single group of SS SD packets under RLC and non-coding schemes. We note that due to simplifying assumptions made in the model derivation, the models not only underestimate the delivery delays under both schemes, but also underestimate the performance difference between them.

The benefit of RLC observed in this paper is similar in spirit to that of rumor mongering ( [START_REF] Deb | Algebraic Gossip: A Network Coding Approach to Optimal Multiple Rumor Mongering[END_REF][START_REF] Borokhovich | Tight Bounds for Algebraic Gossip on Graphs[END_REF]). For a network under the so called random phone call communication model, where at each time step, each node communicates with another node selected uniformly at random among all the nodes, [START_REF] Deb | Algebraic Gossip: A Network Coding Approach to Optimal Multiple Rumor Mongering[END_REF][START_REF] Borokhovich | Tight Bounds for Algebraic Gossip on Graphs[END_REF] derived asymptotic bounds for the time to disseminate multiple messages under both RLC and non-coding schemes.

Finally, [START_REF] Lima | Topology Matters in Network Coding[END_REF] presented a preliminary investigation on the effect of topology on the RLC performance. Simulation results for different graphs (Erdös-Rényi, Random Geometric graph, grid, Watts-Strogatz) and the case where there is a single unicast flow in the network were presented.

Conclusions

In this paper we investigate the benefits of applying random linear coding to unicast applications in resource constrained DTNs. Due to its frequent network disconnection and rapidly changing topology, the key challenge for unicast routing in DTNs is distributed packet transmission scheduling and buffer management. Because of its higher degree of randomness compared to non-coding schemes, RLC schemes increase the probability that a node forwards/keeps information useful for the eventual delivery to the destination.

More specifically, for the case of a single group of packets (SS SD) propagating in the network, RLC reduces the group delivery delay in comparison to non-coding schemes. In particular it achieves the minimum group delay with probability greater than or equal to (1 -1/q) η . Larger gains are achieved by RLC schemes when resources (bandwidth and buffer space) are severely constrained, when information about the content of other nodes is not available, when the network is highly dynamic and when coding is applied to packets from same unicast flows.

Even though RLC schemes reduce group delivery delay at the price of a larger number of network transmissions, with replication control, RLC improves the trade-off between delivery delay and total number of transmissions. This improved performance trade-off allow RLC schemes to reduce average group delivery delay under multiple continuous unicast flows, with significant performance improvement when node buffer is constrained.

In our study, we have considered that all the information transmitted has to be delivered and then we have considered the group delay as the most important performance metric. There are network scenarios and applications where packet losses may be tolerated or have to be tolerated, so that a more relevant performance metric may be the percentage of packets delivered by a given deadline. In this case applying RLC to the whole group of packets may degrade the performance (as it is suggested by Fig. 3(c)) because RLC basically couples all the packets together, and then in most of the cases the destination either decodes all packets or no packet by the deadline. A possibility is to divide the set of packets to be transmitted into different generations (see Sec. 2.5) and apply RLC to packets belonging to the same generation. For example if we need to transfer 1000 packets, but we are satisfied with receiving 900 packets, we could apply RLC to generations of 10 packets. We plan to investigate more the issue of generation management in future research. Another open question is the consideration of heterogeneous mobility model.

Figure 1 :

 1 Figure 1: Graph representations of a DTN contact trace.

Figure 2 :

 2 Figure 2: Augmented event-driven graph G ′ (L, B, (1, 4, 0, 2)) for calculating minimum group delivery time for (1, 4, 0, 2), with B(u) = 2, u ∈ V.The newly added edges are drawn with dashed lines, and the updated intra-node edge capacity is highlighted using bold font. The maximum flow from (1, 0) to (4) is 2, achieved by the following two paths (1, 0), (1, 1.2), (2, 1.2), (2, 7), (2, 10.2), (4, 10.2), (4), and (1, 0), (1, 1.2), (1, 3.5),(3, 3.5),[START_REF] Ahlswede | Network information flow[END_REF][START_REF] Katti | XORs in the air: Practical wireless network coding[END_REF],[START_REF] Balasubramanian | DTN Routing as a Resource Allocation Problem[END_REF][START_REF] Katti | XORs in the air: Practical wireless network coding[END_REF],[START_REF] Balasubramanian | DTN Routing as a Resource Allocation Problem[END_REF].

21 :

 21 return t(l) // return the time of contact l 22: else 23:

Figure 3 :

 3 Figure 3: CDF of different delay metrics obtained from 100 simulation runs for a DTN with N = 101 nodes, K = 10, homogeneous exponential intercontact time with rate β = 0.0049, bandwidth constraint of b = 1 packet per contact, without replication control

Fig. 3 (Figure 4 :

 34 Fig. 3(a) plots the empirical cumulative distribution functions (CDFs) of the minimum group delivery delay, and of the group delivery delay achieved

Figure 5 :

 5 Figure 5: Impact of bandwidth, buffer constraint and control signaling

Figure 6 :Figure 7 :

 67 Figure 6: Group delivery delay under varying number of On-Off nodes

= 3 Figure 8 :

 38 Figure 8: Group delivery delay under multiple generation case (N = 101 flows with Poisson arrival of groups of K = 10 packets, β = 0.0049, b = 1

Table 1 :

 1

	notation meaning	simulation
			setting
	N	number of nodes in the network	101
	V	the set of nodes	N/A
	L	DTN contact trace	pair-wise Poisson
	β	pair-wise contact rate	0.0049
	K	generation size	10
	λ	group arrival rate to each flow	varies
	b	#. of packets can be exchanged	1
		in each direction during a contact
	B	#. of relay packets a node can store varies
	F q	finite field, q = p n ,	q = 2 8
		p is a prime, n is a positive integer
	H total , η	hop count, and #. of routing	N/A
		decisions along minimal delay paths
	D g	time to deliver a group of packets	N/A
	C	per-packet token number	varies
	C g	per-generation token number	varies

Notations and Simulation Settings originated from a single source and destined for a single destination. Sec. 4 extends the study to multiple source case, and investigates the alternative generation management and the case of multiple continuous unicast flows. Sec. 5 reviews related work, and Sec. 6 concludes this paper.

Contacts can be directed, if two independent wireless channels are used for transmissions in the two directions, or undirected, if the same wireless channel is used for transmissions in both directions and the total capacity can be arbitrarily divided between them. We focus on the first case in this paper.

It is possible for a node to decode one or more original packets before it reaches full rank. This happens for example if its encoding matrix A contains one or more row vectors that have exactly one non-zero coefficient.

If node u knows the encoding matrix of node v through full signaling (Sec. 2.5), it can generate a useful combination using the deterministic algorithm proposed in[START_REF] Jaggi | Polynomial Time Algorithms for Multicast Network Code Construction[END_REF]. We do not consider such possibility in this paper.

We implement the following extension to the basic RLC operation to improve its performance in terms of packet delivery delay: if a relay node can decode one or multiple packets (before it reaches full rank), it forwards the decoded packet(s) (rather than random linear combinations) to the destination.

For example, a network might deploy a RLC scheme that employs normal signaling, utility based transmission scheduling, VACCINE recovery, and K-hop replication control. As these design options affect routing performance and overhead, in our comparison of RLC schemes and non-coding schemes, we adopt similar design options for both of them.

Any utility-based scheme can be adapted to work with RLC schemes so that transmission scheduling and buffer management decision are based on the utilities of generations, instead of individual packet.

[START_REF] Cai | Crossing over the bounded domain: from exponential to power-law intermeeting time in mobile ad hoc networks[END_REF] As verified by simulation, this helps to achieve a better balance in the early phase of the dissemination, when small differences in the number of copies of different packets can be amplified by epidemic diffusion.

The residual capacity of an edge is the difference between its capacity and its current flow value, i.e. how much the flow can still be increased on that edge. The residual capacity of a path is defined as the minimum of the residual capacities of all edges in the path.

When node 1 encounters node 2 at t = 1.2, it has two packets in its buffer, and needs to decide what to transmit, therefore the contact (1, 2, 1.2) involves transmission scheduling. Similarly for contacts(1, 3, 3.5) and(2, 4,

10.2). Transmission during contact[START_REF] Ahlswede | Network information flow[END_REF][START_REF] Balasubramanian | DTN Routing as a Resource Allocation Problem[END_REF][START_REF] Katti | XORs in the air: Practical wireless network coding[END_REF] does not involve scheduling decision as node 3 has only one packet in its buffer at time t = 23.

We focus on a particular generation so that we can talk about the number of tokens and the rank of a node without specifying the generation.

For the MS MD case, as each of the K packets is destined for a different destination, it is more meaningful to consider the average time for each of the destinations to receive the one packet destined for it (i.e., average packet delivery delay), than the time to deliver the last packet in the group (i.e., the group delivery delay).

Flows with a larger number of combinations in the network are propagated more and then get even more resources. The mechanism is similar to that described in Sec. 3.4 for non-coding schemes.