Ramakrishna Gummadi

Laurent Massoulie

Ramavarapu Sreenivas

The role of coding in the choice between routing and coding for wireless unicast

Keywords: Erasures, Feedback, Network Coding, Routing, Capacity

We consider the benefits of coding in wireless networks, specifically its role in exploiting the local broadcast property of the wireless medium. We first argue that for unicast, the throughput achieved with network coding is the same as that achieved without any coding. This argument highlights the role of a general max-flow min-cut duality and is more explicit than previous proofs. The maximum throughput can be achieved in multiple ways without any coding, for example, using backpressure routing, or using some centralized flow scheduler that is aware of the network topology. However, all such schemes, in order to take advantage of the local broadcast property, require dynamic routing decisions for choosing the next hop for each packet from among the nodes where it is successfully received. This choice seems to depend critically on feedback signaling information like queue lengths, or ARQ. In contrast, note that the use of network coding can achieve the same without such feedback, in exchange for decoding overhead.

A key issue to be resolved in making a comparison between routing and coding would be how critical feedback signaling is, for the throughput of routing policies. With this motivation, we first explore how feedback at a given node affects its throughput, with arbitrary rates of its one hop neighbors to the destination. Static routing policies which are essentially feedback independent, are considered. An explicit characterization of the optimal policies under such a feedback constraint is obtained, which turns out to be a natural generalization of both flooding and traditional routing (which does not exploit local broadcast, because the next hop is fixed prior to the transmission). When losses at the receivers are independent (still allowing for dependencies

Introduction

We consider wireless erasure networks, where local broadcast influences the role of coding beyond that of merely dealing with lossy transmissions, namely erasures. We show that feedback signaling is a critical factor that defines the role of coding in this situation, in the sense that it is one way to avoid the extensive feedback signaling that is necessary for routing policies. To characterize this more precisely, we consider a formal notion of restricted feedback signaling and derive the throughput of routing policies with restricted feedback on a two-hop network. This allows us to obtain a lower bound on the throughput when the losses are independent, and also to show that it is possible to have arbitrary degradation of throughput with dependent losses.

Local broadcast refers to the property of wireless systems where a single transmission can potentially address a group of clients. Although this is implicit for any wireless transmission, abstractions like the protocol model assume a graph based model in which local broadcast is essentially treated as interference (e.g. [START_REF] Arikan | Some complexity results about packet radio networks[END_REF][START_REF] Gupta | The capacity of wireless networks[END_REF][START_REF] Gummadi | Feasible rate allocation in wireless networks[END_REF][START_REF] Gummadi | Computing the capacity region of a wireless network[END_REF] and many others). In reality, local broadcast represents a diversity gain associated with the channel that could be exploited by either a well-adapted routing scheme or by network coding. In general, coding in the network has two distinct roles in the absence of this local broadcast feature. The first arises from the fact that even without any losses, information flow is fundamentally different from commodity flow, an aspect that points to the field of network coding [START_REF] Yeung | Information Theory and Network Coding[END_REF], starting with the pioneering work of [START_REF] Ahlswede | Network information flow[END_REF]. In wireline settings, network coding addresses strictly more general settings than that of a unicast transmission. On the other hand, forward error correction (FEC) addresses another aspect that stems from lossy transmissions. The role of coding in the context of wireless broadcast is something that needs to be distinguished from the previous two concerns, which are relatively better understood. Notably, in this context, the actual performance of optimal coding schemes is better articulated than are the limits of routing policies, both with and without restrictions on feedback signaling. This creates an avenue to discuss the role of coding by way of a better understanding about the limits of optimal routing schemes and then contrast it with optimal coding schemes.

In this paper, we consider the role of coding, specifically in exploiting the local broadcast property of the wireless medium. We first argue that for unicast, the throughput achieved with network coding is the same as that achieved without any coding. This argument highlights the role of a general max-flow min-cut duality and is more explicit than previous published proofs of this fact. The maximum throughput can be achieved in multiple ways without any coding, for example, using backpressure routing, or using some centralized flow scheduler that is aware of the network topology. However, all such schemes, in order to utilize the local broadcast property, require dynamic routing decisions for choosing the next hop for each packet from among the nodes where it is successfully received. This choice seems to depend critically on feedback signaling information like queue lengths, or ARQ. In contrast, the use of network coding can achieve the same without such feedback, in exchange for decoding overhead.

A key task in comparing routing and coding is to assess the importance of feedback signaling to the throughput of routing policies. With this motivation, we explore how feedback at a given node affects its throughput, for an arbitrary vector of given rates of its one hop neighbors to the destination. Static routing policies which are essentially feedback independent, are considered. An explicit characterization of the optimal policies under such a feedback constraint is obtained, which can be interpreted as a natural generalization of both flooding and traditional routing (which does not exploit local broadcast, because the next hop is fixed prior to the transmission). When losses at the receivers are independent (still allowing for dependencies on transmissions by two different nodes, to model interference), the reduction in capacity due to constraining the feedback is limited to a constant fraction (e -1 = 37%) of the coding capacity, and gets arbitrarily close to optimal as the capacity itself is low. This result is also extended to a more general version on feed-forward networks without any assigned rates of the one hop neighbors to the destination. However, if there are dependencies in the losses seen by receivers from a single broadcast, the reduction could be arbitrarily bad, even with just two hops.

Network coding was originally introduced in [START_REF] Ahlswede | Network information flow[END_REF] as a general framework to achieve the optimal multicast rate from a data source to a set of receivers in wired networks. In contrast to "store-and-forward," also called "routing" operation, network coding performs recombinations of data packets at network nodes, while the former operation never alters original packets. Since then, many other applications of network coding have been identified. In particular, at a practical level, it has been considered in the context of wireless networks [START_REF] Chachulski | Trading structure for randomness in wireless opportunistic routing[END_REF] for unicast communications, where such a wireless setting was identified as an especially good candidate for network coding because of the local broadcast property. The wireless scenario of [START_REF] Chachulski | Trading structure for randomness in wireless opportunistic routing[END_REF] features lossy transmissions as well as local broadcast, although it is not specific to the erasure channel. The experimental evaluations of [START_REF] Chachulski | Trading structure for randomness in wireless opportunistic routing[END_REF] show benefits of network coding over routing policies in terms of the transmission rates achieved. However, Smith and Hassibi [START_REF] Smith | Wireless erasure networks with feedback[END_REF] prove that in any erasure network, there exists a policy that can achieve capacity with no coding. This raises the question: Are there any benefits of network coding over routing in wireless unicast communications? If so, where do they stem from, and how large can they be?

In a nutshell, we show that the benefits of coding over routing depend on the extent of available feedback signaling and characterize the relation. Our first contribution is a simpler argument, using linear programming (LP) duality, that the maximum routing throughput in the case of wireless unicast is the same as the rate achieved with coding. Using this, it is shown that backpressure routing achieves not only the optimal throughput among routing policies, but also more generally across policies that involve coding. However, backpressure policy performs a very dynamic routing of each packet through the network, and requires exchanging queue lengths from all neighbors at every step. This motivates an investigation into the fundamental limits of static routing policies which do not need extensive feedback signaling. We study this tradeoff and quantify the limits imposed by an appropriately defined notion of restricted feedback.

Consider the following extreme case to motivate the analysis (see Figure 1): There are m distributed agents with each agent holding a copy of a set of m distinct packets (which they all received from the source). With full coordination, they can schedule all the m packets in one transmission each by avoiding duplication. However, if we restrict their choice to be made in a distributed manner without coordination, the total number of distinct packets covered by a random choice at each relay approaches 1-(1-1/m) m → 1e -1 , thus leading to only 63% throughput. 100% throughput could be achieved by either (i) making coordinated choices among relay nodes through conferencing among all the relays, or (ii) letting each node send an independent random linear combination of all m packets. In other words, network coding seems to be essentially solving a distributed synchronization problem without the need for any feedback signaling. The above synchronization constraint is modeled as the feedback independent routing (FIR) restriction (see Definition 6): informally, this says that the decision of whether a node chooses to forward a packet should not depend on erasures at other nodes. In all examples of policies that achieve the capacity without any coding, this information is implicitly utilized based on the feedback signaling. Under the FIR restriction, we show that the optimal policies are characterized as tagging policies where each packet being broadcast is assigned multiple next hops. Tagging policies can be considered a generalization of both flooding (where every broadcast packet is routed by everyone that receives it), and traditional routing (where each packet is routed only by a specific receiver chosen prior to the broadcast). When transmissions are subject to mutually independent losses 1 at the receivers (but still possibly allowing for dependences of losses for packets transmitted by two different nodes), even when restricted to feedback independent routing, it is possible to achieve at least 63% of the capacity. In fact, as the capacity, C * → 0, the throughput achieved becomes 100% of C * in the limit. For a general feedforward network with h + 1 hops in which all nodes are restricted to operate under a similar routing constraint, we show under a similar independence condition for link losses (but allowing dependence across different broadcasts) that the reduction in throughput is lower bounded as f h (C * ), where f (x) = 1e -x . Thus, for a limited number of hops, and when the capacity is low to begin with, one can achieve close to optimal throughput without actually making dynamic routing choices. One might imagine that dependencies in link losses supply implicit information about other link losses, and therefore allow better throughput compared to independent losses. But this is not true, as we show a counterexample with dependent link losses for which static feedback independent routing capacity is arbitrarily bounded away from the network coding capacity even for a 2-hop network. One of the implications in this conclusion is that, when feedback is constrained, coding in the network could be unavoidable to achieve non-vanishing throughput.

P(S,i) P(i,D) S D m relays

Related Work

The merits of routing versus coding have been extensively studied in the context of wireless, both theoretically and by experiments. The following two lines of work deal with the ways in which local broadcast can be exploited: (i) By using coding: This has been investigated in [START_REF] Lun | On coding for reliable communication over packet networks[END_REF][START_REF] Dana | Capacity of wireless erasure networks[END_REF][START_REF] Chachulski | Trading structure for randomness in wireless opportunistic routing[END_REF]. The advantage of using network coding to exploit local broadcast is the lack of a need for sophisticated coordination and/or routing choices among the nodes. The price to pay for this is the decoding complexity. (ii) By making dynamic routing/flooding choices along with rich feedback signaling: This was the path taken in [START_REF] Biswas | Opportunistic routing in multi-hop wireless networks[END_REF][START_REF] Smith | Wireless erasure networks with feedback[END_REF][START_REF] Neely | Optimal backpressure routing for wireless networks with multi-receiver diversity[END_REF]. The maximum throughput in an information theoretic sense for the wireless erasure network (WEN) model was studied in [START_REF] Dana | Capacity of wireless erasure networks[END_REF] and was shown to be equal to the appropriate hypergraph min cut, denoted C * . In [START_REF] Smith | Wireless erasure networks with feedback[END_REF], for the unicast wireless setting, a flooding based policy with network wide instantaneous broadcast of the identity of each packet received at the destination was shown to achieve C * . Using this, [START_REF] Smith | Wireless erasure networks with feedback[END_REF] makes an important observation that coding is in fact not necessary for achieving a throughput equal to the capacity in wireless unicast settings. The model used by Smith and Hassibi differs slightly from ours, in the sense that they consider a continuous time data arrival model, but it is not surprising that the same result holds for the discrete arrival model. As one of our contributions, we provide a more fundamental reason based on max flow min cut equivalence. In [START_REF] Neely | Optimal backpressure routing for wireless networks with multi-receiver diversity[END_REF], backpressure routing (requiring rich feedback signaling to perform routing) was shown to be an optimal routing plus scheduling policy in a much more general context taking into account interference effects. In general (i.e. for multicast), [START_REF] Sundararajan | Feedback-based online network coding[END_REF] proposes the use of feedback together with network coding for online decoding. In our work, since we consider a single unicast flow throughout, our results are relevant only to intra-session coding. In contrast, when using network coding across multiple parallel flows as in [START_REF] Katti | XORs in the Air: Practical Wireless Network Coding[END_REF], the situation corresponds to inter-session coding.

The Wireless Erasure Network Model

Let G = (V, E) be a directed graph. Let N (i) = {j ∈ V : (i, j) ∈ E}.
We consider a wireless network that operates on this graph over time t ∈ {0, 1, 2, . . .}. For each t, a node can "broadcast" to its neighbors. The network is subject to probabilistic constraints on the successes of these broadcasts. Specifically, at any given time, t, for each i ∈ V, Z ⊆ N (i), let χ(i, Z, t) denote a {0, 1} random variable that represents the following:

χ(i, Z, t) =      1 , if broadcast from node i at time t is successful to Z,
and fails to N (i)\Z 0 , otherwise The random variables χ can be arbitrarily correlated across the argument i, which allows for modeling arbitrary interference constraints, but we will assume that they are independent across t. For example, this could model the situation in the random access scheduling, where at each time slot, there is a probability that a given node actually transmits, with the transmission being successful if and only if no other node in its interference radius is simultaneously active. Note that, for Z, we have:

Z⊆N (i) χ(i, Z, t) = 1 ∀i, t. We define: c(i, Z) = E[χ(i, Z, t)]
∀t. Thus, we are given a network topology along with c(i, Z) as the capacities. Our analysis will be impervious to the correlations across i, so we will not explicitly specify them. An interesting special case of the above model is to have link (i, j) successful with probability p(i, j), with losses from i to each of the neighbors in N (i) being independent.

We then have:

c(i, Z) = j∈Z p(i, j) j∈N (i)\Z (1 -p(i, j))
We consider a single unicast flow. However, the insights obtained are also general enough for multiple competing flows, with each flow assigned a fixed fraction of the link capacities and a comparison with intra-session network coding in such a scenario. Thus, without loss of generality we assume a source, S, and destination, D. The source has an infinite set of packets indexed over the integers, intended for replication at D. For any v ∈ V , let α v (t) denote the number of distinct packets that were replicated at node v till time slot t.

Definition 1 (Routing policy, P). A routing policy P decides for each node i ∈ V , and time t ∈ {0, 1, . . .}, a packet to be transmitted from among the α i (t -1) choices in its possession.

Definition 2 (Capacity). The throughput of a policy P is defined as:

C(P) = lim inf t≥0 E[α D (t)] t
The capacity is the highest possible throughput C sup P C(P).

A Max Flow Characterization

A key observation is that any policy which uniquely routes each packet without keeping multiple copies can be represented by a valid flow on the throughput constrained graph. In the linear program defined below, each feasible solution represents a policy that routes a fraction proportional to r(i, j, Z) of successful broadcasts from i to Z uniquely to j ∈ Z. The term {Z∈N (i):j∈Z} r(i, j, Z) represents the net flow from i to j. The optimum value of the linear program (LP) then represents the throughput achieved.

Definition 3 (F, the maxim flow value). Let P denote the set of all S -D paths in G. We define the F for a given broadcast capacitated graph as the optimum value of the following LP:

F = max p∈P x p (1)
Subject to:

x p ≥ 0 ∀ p ∈ P r(i, j, Z) ≥ 0 ∀ {(i, j, Z) : (i, j) ∈ E, j ∈ Z ⊆ N (i)} {p∈P :(i,j)∈p} x p - {Z∈N (i):j∈Z} r(i, j, Z) ≤ 0 ∀(i, j) ∈ E j∈Z r(i, j, Z) ≤ c(i, Z) ∀ {(i, Z) : Z ⊆ N (i)} Let x * p , r * (i, j, Z
) denote the optimum solution to the above LP. It is straightforward to show that this capacity can be achieved by the following policy:

Definition 4 (P f s , the flow splitting policy). Any packet transmitted by node i, and received by the set Z ⊆ N (i) of its neighbors is "routed" uniquely to j ∈ N (i) with probability r * (i,j,Z) k∈Z r * (i,k,Z) (thus ensuring that at most one copy of each distinct packet is being transmitted at any point).

We now consider the min cut appropriate for the model by considering the probability that at least one of the nodes across the cut receives a transmission.

Definition 5 (Minimum cut, C * ). A Cut is a disjoint partition of V into A and Ā with S ∈ A and D ∈ Ā. The capacity of the cut is then:

C(A) = i∈A,Z⊆N (i),Z∩ Ā =φ c(i, Z)
The minimum cut is:

C * = min A C(A).
It is easy to argue that C * is an upper bound on the throughput for any scheme even with coding, and was in fact shown to be equal to the information theoretic capacity of the WEN in [START_REF] Dana | Capacity of wireless erasure networks[END_REF]. Thus, C ≤ C * , where we remind that C stands for the routing capacity and C * stands for the min cut, which is equal to the capacity with coding, namely the information theoretic capacity. Based on a duality argument analogous to the classical max flow min cut theorem, the following can be shown:

Theorem 1. F = C * = C
Proof. Consider the dual program for the LP at Equation (1) with dual variables b(i, Z) for each i ∈ V, Z ⊆ N (i) and y(i, j) for each (i, j) ∈ E. We have:

DU AL * = min i∈V,Z⊆N (i) c(i, Z)b(i, Z) (2)
Such that:

{(i,j)∈p} y(i, j) ≥ 1 ∀ p ∈ P (3) -y(i, j) + b(i, Z) ≥ 0 ∀{(i, j, Z) : (i, j) ∈ E, j ∈ Z ⊆ N (i)} y(i, j) ≥ 0 ∀(i, j) ∈ E b(i, Z) ≥ 0 ∀(i, Z) : i ∈ V, Z ⊆ N (i) (4)
Consider the mincut as written in Equation ( 5), and let

A * , Ā * denote this cut. Let y * (i, j) = 1 if i ∈ A * , j ∈ Ā * and 0 otherwise. Similarly, let b * (i, Z) = 1 if i ∈ A, Z ∩ Ā * = φ
and 0 otherwise. Then, it can be verified that this defines a feasible solution to the dual LP above, and that i∈V,Z⊆N (i) c(i, Z)b * (i, Z) = C * . Thus,

C * ≥ DU AL * (5)
Now consider an integral constrained version of the above dual:

DU AL * = min i∈V,Z⊆N (i) c(i, Z)b(i, Z) (6)
Such that:

{(i,j)∈p} y(i, j) ≥ 1 ∀p ∈ P (7) -y(i, j) + b(i, Z) ≥ 0 ∀{(i, j, Z) : (i, j) ∈ E, j ∈ Z ⊆ N (i)} (8) y(i, j) ∈ {0, 1} ∀(i, j) ∈ E b(i, Z) ∈ {0, 1} ∀(i, Z) : i ∈ V, Z ⊆ N (i) (9)
Let y * , b * define the optimal solution to the above integral constrained LP. Then, define A * = {i ∈ V : ∃ a path, p, from S to i such that {(i,j)∈p} y * (i, j) = 0}. Then, D / ∈ A * due to Equation [START_REF] Chachulski | Trading structure for randomness in wireless opportunistic routing[END_REF], and thus A * defines an (S, D) cut. Furthermore, from Equations ( 8) and ( 6), we get C(A * ) = DU AL * . This implies that

C * ≤ DU AL * (10)
To summarize, we so far have:

F = DU AL * ≤ C ≤ C * ≤ DU AL * (11)
If we are able to argue that the constrained LP indeed achieves the optimum (the details of this are given in Lemma 2), we would then have DU AL * = DU AL * , implying that all quantities in Equation ( 11) are the same. 2), and let y * (i, j), b * (i, Z) denote the optimal solution which achieves DU AL * . Consider a graph with edge lengths given by y * (i, j) and let d(i) length of the shortest path from S, with edge lengths given by y * (i, j). Let λ ∈ (0, 1) be chosen uniformly and define:

A * = {i ∈ V : d(i) ≤ λ}
This defines a cut with probability 1, since d(S) ≥ 1 from Equation (3).

Then:

E[C(A * )] = E[ i∈A * ,Z⊆N (i),Z∩ Ā * =φ c(i, Z)] = E[ i∈V,Z⊆N (i) c(i, Z)✶{i ∈ A * , Z ⊆ N (i), Z ∩ Ā * = φ}] = i∈V,Z⊆N (i) c(i, Z)P i ∈ A * , j ∈ Ā * for some j ∈ Z = i∈V,Z⊆N (i) c(i, Z)P (d(i) ≤ λ, d(j) > λ for some j ∈ Z) = i∈V,Z⊆N (i) c(i, Z)(max j∈Z d(j) -d(i)) + (∵ λ is uniform) ≤ i∈V,Z⊆N (i) c(i, Z)(max j∈Z y * (i, j)) ( traingle inequality ) ≤ i∈V,Z⊆N (i) c(i, Z)b * (i, Z) ( from Equation (4)) = DU AL *
Thus, coding in the network is not necessary to achieve the optimal throughput in unicast, assuming unconstrained feedback signaling. This fact was also argued by [START_REF] Smith | Wireless erasure networks with feedback[END_REF] in a closely related continuous time data arrival model (and conjectured and verified by simulation for the discrete time model that we consider). This was accomplished by considering a policy which involves flooding the network with each packet until at least one copy reaches the destination and subsequently using a network wide feedback signal to delete these copies every time the destination receives a new packet. It was shown that such a policy stabilizes the network for all rates below the C * using Lyapunov stability argument. Lemma 3 shows that a distributed backpressure scheme which routes each packet to the least loaded neighbor (thus, avoiding multiple copies) also achieves the information theoretic min cut capacity, C * . This is also suggested by Theorem 1 in conjunction with Neely's result of optimality of backpressure routing schemes in a context that involves power control and with a different interference model [START_REF] Neely | Optimal backpressure routing for wireless networks with multi-receiver diversity[END_REF]. Lemma 3. Consider a Markov chain defined on the network as follows: Each node has a queue of packets. New packets arrive to the queue at the source according to a Bernoulli process of rate λ. For any t, i, Z such that χ(i, Z, t) = 1, the backpressure policy routes a packet from node i to a node j such that queue size difference is maximized (subject to being positive). If λ < C * , the Markov chain thus obtained is stable (positive recurrent).

Proof. The proof follows along the lines of [START_REF] Tassiulas | Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[END_REF] using a quadratic Lyapunov function and Foster's condition to show that the Markov chain is positive recurrent. Packets are injected at the source node according to a Bernoulli i.i.d. process with mean λ < C * . We shall use the potential, V (t) = n i=1 q 2 i (t), where i represents an index over the n nodes in the network and q i (t) represents the number of packets that are held at node i. Let {F t } t≥0 be a filtration adapted to the queue length process. By Foster's theorem (see [START_REF] Tassiulas | Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks[END_REF] and the references therein), a sufficient condition for stability is to show that that the Lyapunov drift E[V (t + 1) -V (t)/F t ] < 0 when V (t) is sufficiently large. Let q(t) denote the n dimensional row vector with q i (t) being the i th element. Let R be the adjacency matrix of dimension n × L (where L = |E|, the number of links) for the given graph (i.e., the (i, l) th element, r(i, l) is 1(-1) iff the link l starts(ends) at i, and 0 otherwise). Let E(t) denote the L dimensional indicator vector denoting the subset of links on which packets were routed by the backpressure policy, and let A(t) denote the arrival process indicator vector, i.e. the element of A(t) corresponding to the source is the Bernoulli random variable with mean λ and all other elements are 0. Then, the queue lengths evolve according to q(t + 1) = q(t) + R E + A(t). Thus (with . denoting the usual dot product of vectors):

V (t + 1) -V (t) = q(t + 1).q(t + 1) -q(t).q(t) = (R E(t) + A(t)).(2q(t) + RE(t) + A(t)) ≤ (n + 1) 2 + 2(q(t).RE(t) + q(t).A(t))
Since the first term above is constant over time, showing that the second term has a large negative drift for large queue lengths is sufficient (since large potential implies large queue length under connectivity assumptions on the graph). Let W(t) denote the L dimensional vector where the l th element denotes the queue length difference for the l th link. Then, q(t).RE(t) = -W(t).E(t). Hence, we only need to argue that E[-W(t).E(t)+q(t).A(t)/F t ] has a negative drift. E[q(t).A(t)/F t ] = q(t).A where A is a vector where the element corresponding to the source is λ and all other elements 0. Since λ < C * , it follows from the max flow interpretation of Theorem 1 that there exist variables r * (i, j, Z) satisfying the constraints of the linear program given by Equation (1), and an ǫ > 0 such that q(t).A ≤ (1-ǫ)W(t).f * , where the component of f * corresponding to link l = (i, j) is f * l = {Z∈N (i):j∈Z} r * (i, j, Z). Let e * (t) denote the indicator vector of dimension L, for the routing selected by the flow splitting policy, P f s given in Definition 4. Then, W(t).f * = E[W(t).e * (t)/F t ]. Thus,

E[-W(t).E(t) + q(t).A(t)/F t ] = E[-W(t).E(t) + (1 -ǫ)W(t).e * (t)/F t ] = E[-W(t).E(t) + W(t).e * (t)/F t + /F t ] -ǫE[W(t).e * (t)/F t ]
Here, F t + denotes the sigma algebra that contains information about the successes on links at time t in addition to the queue length process until time t, and thus, F t ⊆ F t + ⊆ F t+1 . The first term is non-positive because the backpressure policy minimizes W(t).E(t) among all possible options conditioned on the information available on the link successes and the queue lengths (which is what conditioning on F t + denotes). The second term takes arbitrarily large negative values for large V (t) for any fixed ǫ > 0, and thus, we have the required negative drift.

Formalizing a Notion of Restricted Feedback

While we have so far discussed schemes that can achieve the unicast capacity in a wireless network without the need for coding, employing coding in the network can achieve the capacity without using feedback. This calls for an understanding of the inherent limits to the achievable throughput when we restrict the exploitation of feedback in the choice of routing policies. The decision of whether to forward a packet further at a given node should ideally be made without considering the erasure events on other links (this is not the case with any of the routing schemes we have discussed so far which achieve the maximum throughput). In this context, we first fix the vector of rates that the one hop neighbors can support to the destination simultaneously and study how feedback constrained routing affects the overall throughput from the source. The most obvious visualization of this is a network in which the source and destination are assisted by relays which do not communicate within themselves (Figure 1).

Let

c(Z) = E[χ(S, Z, t)] for Z ⊆ [m]. Let p(S, i) = Z⊆[m]
:i∈Z c(Z) denote the probability that the a packet transmitted from S is received at i successfully. We shall let p(i, D) denote the long-term throughput that relay i can support to the sink D. Given a generalized routing/flooding policy, we shall use the {0, 1} random variables, r i (p), r * i (p) which denote the following events:

1. {r i (p) = 1} ⇐⇒ Packet transmitted in time slot p from the source (which shall henceforth be referred to as packet p) was received successfully by relay i. We assume that the source attempts broadcast of distinct packets at each time slot without any loss of generality (e.g., by employing appropriate source coding, or because it has an unlimited stream of useful packets). 2. {r * i (p) = 1} ⇐⇒ Packet p is routed to D via relay i. Note that: (1)

{r * i (p) = 1} ⇒ {r i (p) = 1}. (2) It is possible that r * i (p) = 1 for multiple i.
We will now explicitly describe what we mean by feedback independent routing. Definition 6 (Feedback independent routing (FIR)). ∀p ∈ {0, 1, . . .}, ∀A, B ⊆ [m] such that A ∩ B = φ, the given routing policy satisfies the F IR restriction if, conditioned on {r i (p) = 1 ∀ i ∈ A}, the following two collections of random variables: {r * i (p)} i∈A and {r i (p)} i∈B , are mutually independent. This condition is essentially equivalent to assuming a lack of feedback to the broadcasting node. Technically, lack of feedback is sufficient but not entirely necessary to satisfy this. While this distinction is subtle, it might be noted that one does not violate FIR by using rudimentary feedback for purposes other than routing. Nevertheless, source coding is a convenient way to completely eliminate feedback. As for the first hop nodes, we merely consider them as black-boxes that support some arbitrary vector of simultaneous rates to the destination. For a 2-hop relay network, these simultaneous rates could be achieved by employing any capacity achieving scheme for a single erasure channel, i.e. either by (1) feedback to the relays, or (2) forward erasure coding (FEC) at each relay. 2We have so far discussed three policies which achieve capacity without any coding: (1) the flow splitting policy P f s in Definition 4, (2) the backpressure policy in Lemma 3 and (3) the policy of [START_REF] Smith | Wireless erasure networks with feedback[END_REF]; but they all involve a heavy interaction between feedback and routing, and hence fail to satisfy the given constraint.

Capacity under Feedback Independent Routing Constraint

Definition 7. The capacity with feedback independent routing, C R is defined as the maximum throughput as in Definition 2, restricted to policies P satisfying Definition 6.

For FIR, one extreme is to tag each packet with a single relay (this is how routing is done in practice in the 802.11 protocol). This could be suboptimal because it does not exploit the local broadcast advantage. The other extreme is to flood every packet to all relays. This could be suboptimal when the relays do not have enough capacity to forward all packets they received to the destination. They will then have to make distributed decisions on which packets to forward from among the received packets, leading to redundant transmissions and a hence a decreased throughput. As we will show, when we restrict to FIR, the maximum throughput is achieved within a subclass of policies that we shall call the tagging policies. A tagging policy assigns to each packet a subset of relays, Z ⊆ [m], which is independent of any feedback. We represent the fraction of packets that are tagged with Z as t(Z). A relay i that receives a packet successfully routes the packet without dropping it if and only if i ∈ Z. These packets are retransmitted until the destination receives them. The capacity of such policies can be expressed via the linear program below, where each feasible solution corresponds to a specific tagging policy. The last constraint in the LP states that the arrival rate of packets to any relay's queue has to be less than its forwarding capacity to the destination.

C T = max Z,Z ′ ⊆[m]:Z∩Z ′ =φ t(Z)c(Z ′ ) ( 12
)
Subject to:

Z⊆[m] t(Z) ≤ 1; (13) p(S, i)   Z⊆[m]:i∈Z t(Z)   < p(i, D) ∀i ∈ [m] ( 14
)
All packets that reach a relay successfully and have the relay in the tag will eventually reach D because of the constraint in Equation ( 14) (which implies that the queue of packets at each relay is stable). Since the tags are chosen independent of the losses, the probability that a packet is successfully transmitted to some relay which is also included in its tag is Z∩Z ′ =φ t(Z)c(Z ′ ), which can be readily shown to be equal to the throughput of the policy as per Definition 2.

Lemma 4. C R ≥ C T Lemma 4 holds due to the fact that any feasible solution to the LP gives us a tagging scheme whose throughput is equal to the value of the LP.

Optimality of Tagging Policies under FIR

Remarkably, these policies will now also be shown to be optimal in general under the FIR constraint, thus giving us an explicit characterization of C R in the form of Theorem 5.

Theorem 5. C R ≤ C T , implying C T = C R
Proof of Theorem 5. We look at any policy that satisfies F IR and show that it is possible to define appropriate variables that define a feasible solution to the LP in Definition 8, and for which the throughput is upperbounded by the objective function.

Consider any arbitrary policy. We will show that the expected number of distinct packets that reach the destination in k time slots cannot be more than kC T as long as FIR in Definition 6 is satisfied, thus implying that the C R is at most C T . Define:

t(Z) = 1 k k p=1 P r * i (p) = 1 ∀ i ∈ Z and 0 ∀i ∈ [m]\Z r i (p) = 1 ∀ p ∈ [m] (15)
where we use the standard convention of writing P (A∩B)

P (B)
as P ( A B ) for an event B with positive probability. It is easily verified that t(Z) ≥ 0 and Z⊆[m] t(Z) = 1. We will now verify that the third constraint (Equation ( 14)) holds for any i ∈ [m].

kp(i, D) ≥ E[ k p=1 ✶{r * i (p) = 1}] = k p=1 P (r i (p) = 1)P r * i (p) = 1 r i (p) = 1 = p(S, i) k p=1 P r * i (p) = 1 r i (p) = 1 = p(S, i) k p=1 P r * i (p) = 1 r j (p) = 1 ∀j ∈ [m] (using def.6) = p(S, i) k p=1 Z∋i P r * j (p) = 1 ∀ j ∈ Z and 0 ∀j ∈ [m]\Z r j (p) = 1 ∀j ∈ [m] = kp(S, i) Z∋i t(Z) (by definition of t(Z) in Equation (15))
We now calculate the number of distinct packets replicated at D in k time slots.

E[α D (k)] = k p=1 P ({ i∈[m] {r * i (p) = 1}}) = k p=1 Z⊆[m] P r i (p) = 1 ∀ i ∈ Z and 0 ∀i ∈ [m]\Z × P r * i (p) = 1 for some i ∈ [m] r i (p) = 1 ∀ i ∈ Z and 0 ∀i ∈ [m]\Z = k p=1 Z⊆[m] c(Z)P r * i (p) = 1 for some i ∈ Z r i (p) = 1 ∀ i ∈ Z and 0 ∀i ∈ [m]\Z (∵ ∀i ∈ [m]\Z, {r i (p) = 0} ⇒ {r * i (p) = 0}) = k p=1 Z⊆[m] c(Z)P r * i (p) = 1 for some i ∈ Z r i (p) = 1 ∀ i ∈ [m] (using FIR Definition 6) = k p=1 Z c(Z) Z ′ ∩Z =φ P r * i (p) = 1 ∀i ∈ Z ′ and 0 else r i (p) = 1 ∀ i ∈ [m] = k Z⊆[m] c(Z) Z ′ ⊆[m]:Z ′ ∩Z =φ t(Z) = k Z,Z ′ ⊆[m]:Z∩Z ′ =φ t(Z)c(Z ′ )
In general, it is not obvious if C R is strictly less than the general min cut, C * . Indeed, in many cases, these two quantities match, implying that in such cases, not only do we not need any coding, but the capacity can be achieved by optimized tagging schemes that satisfy FIR. For example, consider a network with two relays with success probabilities p(S, 1), p(S, 2), p(1, D), p(2, D) where link losses for the same transmission are independent.

Example 1. If p(S, 1), p(S, 2), p(1, D), p(2, D) are all 1/2, we have: 2(a), C * = 3/4 and from the LP (Equation ( 12)), we can calculate that C R = 3/4. In fact, a flooding policy achieves this rate of 3/4. So there is no reduction in the capacity under FIR.

C({1}) = C({2}) = C({1, 2}) = 1/4. From Figure
Example 2. Consider an example where the cuts are more finely balanced: p(S, 1), p(S, 2) = 1/2; and p(1, D), p(2, D) = 3/8. Again, C * = 3/4, as explained in Figure 2 This optimum throughput of 5/8 under FIR is achieved by routing 25% of the packets exclusively to relay 1, 25% exclusively to relay 2 and the remaining 50% of the packets to both the relays.

(b). Set t({1}) = x, t({2}) = y, t({1, 2}) = z. Then: C R = M ax ( 1 2 x + 1 2 y + 3 4 z) Subject to: x, y, z ≥ 0, x + y + z ≤ 1, x + z ≤ 3/4, y + z ≤ 3/4.

Quantifying the Loss of Throughput under FIR

In this section, we will use the theory from previous sections to obtain results on the throughput attainable under FIR. We will first consider the case where the link losses from a given transmitter seen at its various receivers are independent. Note that this involves no assumptions on interference between two different transmissions. As a critical tool, we will use a flooding policy, which is defined below. Definition 9 (Flooding policy, P F ). Each relay blindly chooses each received packet from the source to be forwarded to the destination with probability min(1, p(i, D)/p(S, i)). In other words, the relay effectively makes a uniformly random selection of a p(i, D)/p(S, i) fraction of its received packets to be forwarded to the destination whenever p(i, D) ≤ p(S, i).

We named the above policy as flooding in a general sense, because every packet that is successfully received is considered for being forwarded at any relay. It is possible that the total number of received packets at each relay could be more than the rate it can support to the destination, in which case P F essentially makes a random selection of packets corresponding the maximum throughput it can support. The throughput of P F can be calculated by evaluating the probability that a packet transmitted by the source in any given time slot reaches the destination along at least one of the m relays. Since these events are independent under our current hypothesis, we have Lemma 6, which is obtained from calculating the probability that any given packet reaches the destination via at least one of the relays. Lemma 6.

C(P

F ) = 1 - i∈[m]
(1min(p(S, i), p(i, D)))

A Lower Bound for Independent Erasures

Using this flooding policy, we now prove a lower bound on C R for a network with arbitrary fixed rates from the first hop forward. This argument explicitly bounds the loss of throughput because of the redundant transmissions arising out of making distributed decisions at each of the relay nodes with arbitrary min cuts when we have independence among link successes. The bound we provide also implies that when the capacity is low, the flooding is almost optimal for independent losses to the first hops. We will provide the proof on a 2-hop network for easier visualization, but the same claim holds for any fixed rates from the first hop to the destination. Theorem 7. Consider the relay network of Figure 3 with independent from the source to the relays.

C R ≥ 1 -e -C *
It follows from this bound that, as

C * → 0, C R /C * → 1
Proof. The argument is based on comparing the throughput of the flooding policy C(P F ) with C * , since P F is a policy that satisfies FIR. We will show that C(P F ) ≥ 1e -C * , which in turn implies the theorem since P F clearly satisfies FIR (Definition 6).

Recall that:

C(P F ) = 1 - i∈[m]
(1min(p(S, i), p(i, D)))

Applying the definition of the mincut (see Figure 3 for illustration), C * , to the network under consideration, we see that

C * = min A⊆[m]   1 - i∈[m]/A (1 -p(S, i)) + i∈A p(i, D)  
Let A * be the arg min over A ⊆ [m] for the above equation, so that:

C * = 1 - i∈[m]/A * (1 -p(S, i)) + i∈A * p(i, D) (16)
Consider any i ∈ A * . By definition of A * , we have:

1 - j∈[m]/A *
p(i, D) ≤ p(S, i) j∈[m]/A * (1 -p(S, j)) ≤ p(S, i) (17)
Thus:

C(P F ) = 1 - i∈[m]
(1min(p(S, i), p(i, D)))

≥ 1 - i∈A * (1 -min(p(S, i), p(i, D)) = 1 - i∈A * (1 -p(i, D)) (∵ p(i, D) ≤ p(S, i) ∀ i ∈ A * from Equation (17)) ≥ 1 - i∈A * e -p(i,D) (∵ 1 -x ≤ e -x ∀ x ≥ 0) = 1 -e -i∈A * p(i,D) ≥ 1 -e -C * (∵ i∈A * p(i, D) ≤ C * from Equation (16))

Extension to Layered Multi-hop Networks with independent losses

The prior analysis characterizes the degradation through the effects of feedback at a single node, given the rates achievable from the subsequent hops in any general network. In this section, we build upon this argument to obtain a bound for arbitrary feed-forward networks where every node is restricted to static routing and without any assumption of achievable rates from the one hop neighbors. Further, we also simulate both flooding and backpressure policies for a layered network with ten hops and plot the results obtained. As illustrated in Figure 4, the feedforward networks have nodes that are divided into layers where broadcasts from any node in layer i are heard only by nodes in layer i + 1.

Source Destination

Theorem 8. For a general feed-forward network with h + 1 hops, subject to feedback independent routing, the capacity is at least f h (C * ) where f (x) = 1e -x and C * is the min cut capacity.

Proof. The argument builds on the analysis in Theorem 7. First, we note that feed-forward networks can be reduced to general layered networks where only nodes at subsequent levels are connected, by introducing dummy nodes with unit capacity links. For such a layered network, we will adopt the convention that the sink is at level 0, and the source is at level h + 1. We will define (i, j) to be the node indexed j at level i. In this notation, the source defining the min cut for the network defining C * 1 in the same sense as it was used in proof of Theorem 7. It can further be shown that g(x 1 + . . . + x n ) ≤ g(x 1 )+. . . g(x n ) by using induction on the exponent of f in the representation of g. Using this fact (and denoting Θ = 1 -i∈[m]/A * (1p(S, i)) for convenience below), we then have:

C ≥ Θ + i∈A * g(r i ) ≥ g(Θ) + i∈A * g(r i ) ≥ g(Θ + i∈A * r i ) = g(C * 1 )

Simulation Results

In this section, we ran a simulation of the flooding policy and the backpressure policy on a layered network with ten layers in total. At each layer, there are ten individual nodes. When a node in layer i broadcasts, each of the nodes in layer i + 1 receives the packet with an acceptance probability p, and these events are assumed to be independent across the nodes. In the case of a flooding policy, every successfully received packet is accepted into the queue of any node, without regard to whether a duplicate of the same packet exists elsewhere in the network. In contrast, the backpressure policy ensures that at most one copy of any given packet is present somewhere in the network, by exchanging queue length information to elect the node with the smallest queue as the unique forwarding node for any given packet after its broadcast event. For convenience, we simulate a network with an identical acceptance probability at all links and plot the ratio of the resultant throughput of the flooding scheme with the throughput of the backpressure policy, as a function of the acceptance probability p. From the plot, it is seen that this ratio converges to one as the p → 0. While this simulation is specific to the network in question, the theory implies that a similar qualitative relation is expected to hold irrespective of the number of nodes in each layer and variable acceptance probabilities, subject to the constraint that all loss events are independent. In the next section, we study the effects of relaxing the independence constraint. Remarkably as we will see in Section 11, even in a two hop network, the ratio of throughput under feedback constraints to that of the unconstrained capacity could be arbitrarily bad, unlike the independent losses case.

A notable observation from the above plot is that the performance of a flooding based policy approaches that of the backpressure throughput (which is equal to the min cut capacity) as the link success probability goes to zero. The ratio of flooding to backpressure throughputs on a layered network example with 10 layers, each with 10 nodes as a function of the link success probability, which is set to be identical across all node pairs.

Dependent Losses

From the previous section, one wonders if we are always assured of a constant factor reduction capacity in general, without either feedback or network coding on at least bounded diameter networks. Naively speaking, this seems plausible because correlations in the losses can only supply the relays with implicit information that might help them synchronize their routing more efficiently while satisfying FIR. This intuition is flawed, as the following counterexample shows that C R → 0 even though the capacity C * = 1. This counterexample can be practically motivated as an extreme case of a situation where most of the time (with probability p to be explicated later) the broadcast channel is bad enough to be actually useful to a very small set of relays but occasionally experiences high strength, in which case most of the relays receive the broadcast. We make use of the characterization of C R from Theorem 5 in showing this fact.

Conclusion

While network coding is necessary to achieve the maximum throughput for multicast connections, this is not the case with wireless unicast. Rather, network coding is a convenient way to solve the distributed routing problem without having to depend on feedback signaling to make complicated routing choices for achieving the maximum throughput. In this context, we analyzed a relay network and quantitatively characterized the limitations of 'static' routing policies that operate in a feedback independent manner. Our characterization allows for explicitly identifying situations when there is no loss of throughput by restricting to such simple routing policies. Further, we show that the reduction in the throughput is controlled when the link losses for a given transmission are independent, and could even be minimal when the capacity is low, on a general feed-forward network. At worst, this is 63% and gets progressively close to 100%, as the capacity itself goes to 0. Thus, in such a situation, network coding delivers no benefit over simpler blind routing policies in the limit of unreliable communication. Nevertheless, highly correlated losses could lead to an unbounded loss even on a 2-hop network. In such a situation, network coding might be unavoidable if we need to be conservative with the feedback.

Figure 1 :

 1 Figure 1: The relay network example.

Lemma 2 .

 2 DU AL * = DU AL * Proof. We use an analogous argument employed in showing the corresponding statement for the classical max flow min cut theorem. The argument considers a probability distribution on the set of all possible cuts and argues that the expected value of C * thus obtained is no more than DU AL * , which in turn implies that DU AL * ≤ DU AL * , thus completing the proof. Consider the dual LP in Equation (

Definition 8 (

 8 Tag capacity, C T ). C T is defined as the optimum value of the following LP with variables t(Z) ≥ 0 where Z ⊆ [m].

  The optimal value can be verified to be 5/8 < 3/4 = C * .

Figure 2 :

 2 Figure 2: Examples.

( 1 -Figure 3 :≤ 1 -

 131 Figure 3: Illustration of a min cut and the set defining A * for this min cut.

Figure 4 :

 4 Figure 4: An illustration of the layered feedforward networks being considered

  Ratio of Flooding-and Backpressure-Throughput #Layers = 10, Simulation Length = 100,000

Figure 5 :

 5 Figure 5:The ratio of flooding to backpressure throughputs on a layered network example with 10 layers, each with 10 nodes as a function of the link success probability, which is set to be identical across all node pairs.

Definition 10 (

 10 Network, N of size m). Let ǫ > 0 = 1 √ m . When the source broadcasts, with probability ǫ, all relays receive the packet and with probability 1ǫ, exactly one of the relays receives the packet. relay to destination, we have:p(i, D) = 1/m ∀ i ∈ [m] Theorem 10. For the network N , C * = 1, but lim m→∞ C R = 0Proof. By computing the mincut, we have C * = 1. We shall now derive an upper bound on the C R which tends to 0 as m → ∞ using Theorem 5. This implies the claim because of Theorem 5. Since c(Z) depends only on |Z|, and the LP 12 is symmetric over i, one can set without loss of generality, t(Z) = φ(|Z|). This implies:Z,Z ′ ⊆[m]:Z∩Z ′ =φ t(Z)c(Z ′ ) =

i.e., the random variables representing the losses events are mutually independent

The key aspect that distinguishes such FEC from network coding is that in the case of FEC, the destination has to be able to decode the data being encoded by each relay independently from the transmissions received from that specific relay alone, whereas with network codes, the relay only needs to collect the packets from all relays and jointly decode them.

is assumed to be (h + 1, 0), and the sink is (0, 0). Given any policy, P, we define P(i, j) as the rate at which distinct packets are streaming to the sink through (i, j) . For example, P(h + 1, 0) is the throughput of the policy.

Consider ψ, the flooding policy satisfying FIR, and compare it with the splitting policy, P f s in Definition 4: A node b queues the packets that it receives from node a in proportion to the rate r * (a, b) . = Z⊆N (a) r * (a, b, Z) with r * as in Definition 4. Note that this is a static calculation and involves no feedback unlike P f s or the backpressure policy, which requires queue length information to decide every routing step. For such a policy, we make the following claim, which can be shown using induction on i.

The claim follows easily for i = 1. Assume that it holds for some i.

We will look at a node (i + 1, j) which is connected to (i, j 1 ), . . . , (i, j k ). Consider two different 2-hop networks both with (i + 1, j) as the source and (i, j 1 ), . . . , (i, j k ) as relays with the same link characteristics as the feedforward network for the first hop. To describe the second hop capacities, we will use the assumption that both P f s and ψ choose the same fraction of the incoming capacities from various nodes for the forward throughput. Let α t be the fraction of incoming rate that is chosen by node (i, j t ) for the throughput from (i + 1, j). For the second hop, the first and second networks have capacities (α 1 ψ(i, j 1 ), . . . , α k ψ(i, j k )) and (α 1 P f s (i, j 1 ), . . . , α k P f s (i, j k )) respectively. Let C * 1 , C * 2 be the respective C * 's. Now, we can use Theorem 7 to argue that ψ(i + 1, j) ≥ f (C * 1 ). Using the induction hypothesis, we know that α t ψ(i, j t ) ≥ α t f i-1 (P f s (i, j k )). It can be shown under this condition (using Lemma 9) that

, thus completing the induction hypothesis. Lemma 9. Following the notation used in Section 5, consider a two-hop relay network with parameters c(Z) for the first hop and r i : i ∈ [m] as the rates for the second hop. Let the min cut of this network be C * 1 . Replace the second hop rates by α i g(r i /α i ) where g(x) = f n (x) for some n with f (x) = 1e -x . The new min cut C * 2 ≥ g(C * 1 ). Proof. First note that for each α > 0, for the given g, we have α i g(r i /α) ≥ g(r i ), which can again be shown using induction on the exponent of f corresponding to the given g. Therefore, it is sufficient to show that the network with second hop capacities, g(r i ), has a mincut, C ≥ g(C * 1 ). Let A * be the set


F Treyssède
email: fabien.treyssede@lcpc.fr

Vibroacoustic interface conditions between prestressed structures and moving fluids

n = 4 n = 3 n = 2 n = 0 n = 1