Gabriel Popa
email: gpopa@tik.ee.ethz.ch

Eric Gourdin
email: eric.gourdin@orange-ftgroup.com

Franck Legendre

Merkouris Karaliopoulos

On Maximizing Collaboration in Wireless Mesh Networks Without Monetary Incentives

In distributed network settings, where nodes are not under the control of a single administrative entity, the fulfillment of fundamental network operations is heavily dependent on their cooperation. Nevertheless, individual interests in combination with resource constraints do not always encourage cooperative behavior. In this work, we focus on static Wireless Mesh Networks (WMNs) and address the issue of selfishness in packet forwarding. Firstly, we model the dependencies that emerge in these networks as a result of their topology, traffic demand matrix, and route selection and determine the conditions for the natural emergence of collaboration, without the need of (monetary) incentives. We then assess the achievable collaboration levels, i.e., percentage of traffic demands (flows) that can be served thanks to the emerging collaboration, in both synthetic and real-world WMN topologies under shortest-path routing. Our results show that the cooperation improves when the number of flows increases. Yet, certain topological characteristics (marginal nodes, node degree distributions) make full cooperation difficult to achieve for the average case and bound it asymptotically. Finally, and motivated by these results, we use our dependency model to drive the selection of routes in the network. We cast the routing problem as a mixed-integer programming problem, which tries to maximize the collaboration level in the network. Our study investigates the resulting tradeoff among network throughput, served traffic flows, and routing stretch factor.

I. INTRODUCTION

As communication devices available to individuals have become more powerful and feature-rich, the communication process itself has evolved towards a user-centric paradigm.

Perceived as a component of this trend, wireless mesh networks aim at providing a comprehensive set of services to users. They are characterized by lack of a central authority and offer more degrees of freedom when compared to conventional provider-operated networks. However, wireless mesh networks also introduce a new set of problems imposed by their de-facto distributed nature. In particular, routing algorithms require nodes on a route, acting as relays, to collaborate in forwarding data. These relay nodes, driven by pragmatic considerations (such as limited power on mobile devices), might silently drop packets, thus disrupting in a selfish way the network service.

Even if we consider a static wireless mesh network without any energy constraints (e.g., community network), cooperation still cannot be taken for granted as a substantial bandwidth share has to be allocated to others to relay their traffic.

Researchers have used game-theoretic arguments to argue about the potential for cooperation in WMNs. Felegyhazi et al. [START_REF] Felegyhazi | Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks[END_REF] used a model based on node dependencies to show that the probability of obtaining a poor Nash equilibrium state for cooperation in the network is high, if no incentive-giving mechanisms are in place. Several protocols inspired by game theoretic mechanisms offer monetary incentives to nodes in exchange for their cooperation in forwarding data packets [START_REF] Anderegg | Ad hoc-VCG: a truthful and costefficient routing protocol for mobile ad hoc networks with selfish agents[END_REF], [START_REF] Zhong | On designing incentivecompatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretical and cryptographic techniques[END_REF], [START_REF] Li | Hidden information and actions in multi-hop wireless ad hoc networks[END_REF]. Most of them adapt VCG-based self-enforcing mechanisms to the peculiarities of wireless networks, in order to avoid the potential wrongful signals from selfish nodes.

When acting as relays, nodes collect monetary units, which in turn can be used to request the service of other relays for forwarding their own data.

In our work, we take one step back with respect to these studies, to analyze achievable cooperation when monetary incentives are not available. Similar to the work of Felegyhazi RAWNET 2010 et al. [START_REF] Felegyhazi | Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks[END_REF], we construct a model that will let us assess the potential for cooperation in the network. Nevertheless, we switch from the node space to the traffic demand space; this has been done in order to allow nodes which are sources (or destinations) for different demands to respond individually, on every route, to the perceived presence of non-cooperative behavior on the routes corresponding to these demands. Our demand dependency model uses the fact that both ends of a demand involved in communication are interested in packet forwarding services provided by the relay nodes. We use this model to introduce a metric for the achievable cooperation under given network topology, traffic demand matrix and routing policy.

We then go one step further than prior work in that we actively seek to increase cooperation in the network via routing. The routing function is formulated as a mixedinteger optimization problem, which aims at maximizing the dependencies among traffic flows in the network and, hence, encourage cooperation as a natural choice. We present several optimization models which maximize cooperation while trying to reduce route lengths or to increase the amount of traffic that can be routed.

The paper is structured as follows: we first provide a model of cooperation based on dependency graphs in Section II and evaluate the cooperation levels on synthetic and real-world topologies under shortest-path routing in Section III. We then propose an optimization framework as a basis for the design of cooperation friendly routing in Section IV. We consider various alternative formulations for the routing problem, which can increase cooperation up to 100% by rearranging the routes in the network. We evaluate the tradeoffs introduced by this approach in Section V. Finally, we conclude the paper by outlining the next steps to be pursued in Section VI.

II. MODELING COOPERATION WITH DEMAND DEPENDENCY GRAPHS

This section formulates a criterion for packet forwarding cooperation by looking into the dependencies data flows create among wireless nodes. Our explicit assumptions are that a) nodes have global knowledge of the network topology and available routes therein; and b) nodes cooperate during the route discovery phase.

A. Network Model and Problem Statement

We will represent the wireless mesh network by an undirected graph G = (V, E), where V is the set of nodes and E is the set of radio links between nodes. The traffic demand set K includes all pairs of traffic origin/destination nodes, (s k , t k ) k∈K , where s k , t k ∈ V . Each node can serve as source/destination for one or more demands. The assumption is that a node would not want to offer forwarding services in the network unless it wants to send or receive data from it. We denote by P k the set of feasible routes for demand k (joining s k and t k ) and by P = ∪ k∈K P k the respective set for the full demand set K. A route profile is a set of paths S ⊆ P containing exactly one route p k for each demand k:

|S ∩ P k | = 1, (∀)k ∈ K.
We consider that every demand transports a single unit of traffic load. We assume that a node does not have incentives to cooperate in serving a demand, unless all its own demands are fulfilled, i.e., all flows for which this node is either source or destination are served by the network.

Our objective is three-fold. First of all, we want to obtain a concise description of the dependencies that traffic demands and routing generate among nodes in the network and define a metric for the cooperation level that naturally exists therein.

We treat this in the next two subsections. Secondly, we intend to show the conditions under which conventional routing approaches, such as the shortest path routing policy, favour collaboration. This is covered in Section III. Note that, whereas the traffic demand matrix is an exogenous factor and presented as an input to the network, routes can be controlled and chosen by the latter. Therefore, and this is our main objective, we seek to find and assess route profiles S, such that the number of functional demands (the ones whose routes contain only cooperating relays) is maximized. This is contrary to conventional routing approaches that aim at minimizing some notion of "cost"; therefore, we expect a penalty in terms of route length (routing stretch factor) when compared to shortest-path routing. We elaborate on these routing approaches in Sections IV and V.

B. From Node Dependencies to Demand Dependency Graphs

We say that a given node x ∈ V collaborates with a given demand (s k , t k ), k ∈ K if i) it is part of the route selected by the demand, x ∈ p k , and, ii) it performs packet forwarding on p k . Thus, we can say that nodes s k and t k depend on node x, once a route p k containing x has been selected by demand k. Of course, x can also decide to be selfish. We hence seek to determine under which conditions collaboration emerges naturally because of inter-dependencies.

A route is functional as long as it obtains the collaboration of all the relays on the path. We will consider that the end nodes of a demand k are dependent on (the forwarding performed by) each of the relay nodes on the selected route p k and, for this matter, on their cooperation. These dependencies can be captured by the demand dependency graph that we will consider hereafter, denoted by G dep . For each route profile S, a directed dependency graph G dep (S) = (K, A) is defined as follows: there is one node associated with each demand k ∈ K and a directed arc

(k, k ′ ) ∈ A from demand node k to k ′ exists if path p k is routed (in graph G) over s k ′ or t k ′ or both.
Consider Figure 1(a), which shows a simple network topology with eight nodes, through which four traffic demands need to be served. The demand set is K = {k 1 , k 2 , k 3 , k 4 }, where each demand is a tuple containing the source and destination nodes, k i = {s i , t i }, (∀)i = 1, 4. The route profile under minimum-hop count routing would be S = {p 1 , p 2 , p 3 , p 4 }, where p 1 = {s 2 , t 3 }, p 2 = {t 4 }, p 3 = {s 2 , t 4 } and p 4 = {s 1 }. The dependency graph G dep (S) resulting from {K, S} is depicted in Figure 1(b).

C. Conditions for Cooperation

We outline the necessary and sufficient conditions for collaboration between arbitrary demands in G dep . It follows from Section II-B that if two demands k 1 , k 2 ∈ K are dependent on each other then they will cooperate as long as none has other, unsatisfied dependencies. The assumption is again that the common good is being recognized by the two demands. By extension, we consider that if we have

k 1 , k 2 , k 3 , . . . , k n ∈ K such that (k 1 , k 2 ), (k 2 , k 3 ), . . . , (k n-1 , k n ), (k n , k 1 ) ∈ A, but (∀)k ∈ K, (k i , k) / ∈ A, k i = k, (∀)i = 1, n, then demands k 1 , k 2 , k 3 , . . . k n collaborate fully (through direct and indirect dependencies). If the second condition is not fulfilled and (∃)i ∈ {1, . . . , n}, k ∈ K, k = k j , (∀)j = 1, n such that (k i , k) ∈ A, but this is not a part in a cycle of G dep , then
demand k will not cooperate with k i (at least one node of p k is selfish). Since k i does not obtain the desired service, it will also decide to stop cooperating with k i-1 , the noncooperating behavior spreading to all the demands in the cycle. It follows that two demands k ′ , k ′′ cooperate as long as they are part of a cycle of G dep and every dependency leaving the cycle is also included in a cycle of G dep . For this, we formulate the following equivalent results, noting that overlapped dependency cycles form strongly connected

s 1 t 1 t 3 s 3 t 4 s 4 t 2 s 2
(a) Sample topology with 4 demands

k 1 k 2 k 3 k 4 (
Proposition 2.1: We consider k ′ , k ′′ ∈ K, (k ′ , k ′′ ) ∈ A.
k ′ and k ′′ cooperate if and only if the following three conditions are fulfilled simultaneously:

1. (∃)C, a cycle of G dep , such that (k ′ , k ′′ ) ∈ C; 2. (∃)C k , a cycle of G dep , such that (k ′′ , k) ∈ C k , (∀)(k ′′ , k) ∈ A.

condition 2. applies for any demand k

′′ reachable from k ′ in G dep , recursively.
This can be reformulated as follows:

Proposition 2.2: Demands k ′ , k ′′ ∈ K cooperate (directly or indirectly) if and only if the following conditions are fulfilled simultaneously:

1. k ′ , k ′′ ∈ K are members of the same (maximal) strongly connected component of G dep ;
2. the strongly connected component does not have any outgoing dependencies.

To measure the collaboration level in a given network scenario, we introduce the cooperation ratio F(G, D, S), as the average percentage of functional demands over various random demand sets K of fixed size in network G under given route policy S and demands-per-node ratio D = |K| |V | . The numerator of F equals the number of vertices in the demand dependency graph that fulfill the requirements of Proposition 2.2.

The actual players remain the nodes and for cases when the same node finds itself as either source or destination for multiple demands, then dependencies need to be added between these demands to ensure the cooperation between them when needed.

III. COOPERATION LEVELS UNDER SHORTEST PATH

ROUTING

In this section, we compute the cooperation ratio in various WMN topologies, under shortest-path routing (S ≡ SP ). We examine both synthetic and real-world WMN topologies, varying for each case the demands-per-node ratio, D, as measure of the traffic activity of the network nodes. Results for F(G, D, SP ) are averages of 1000 random demand placement rounds, with D starting from 0.25.

We first study the wireless mesh network used as backhaul for the Rice TFA infrastructure [START_REF]Rice TFA Wireles Network[END_REF], a large scale community network composed of 21 nodes that serves areas with poor Internet connectivity in Houston, TX, United States. Figure 2(a) plots the cooperation ratio with 95% confidence intervals. We observe that the cooperation increases fast for small values of D and then slower as D increases, approaching 90%. As one would expect, as D increases, more dependencies give rise to a denser G dep (S), thus increasing the probability of obtaining fewer larger strongly connected components and decreasing the number of dependencies between them. Nevertheless, when D grows beyond some value, both the functional and non-functional demands increase to similar extent. This is partially an effect of marginal nodes, which have a single link to the rest of the network. Demands from a marginal end node have a lower probability of obtaining collaboration since marginal nodes cannot act as relays on any route. In other words, no other demand can have a route going through marginal nodes under shortest-path routing and, hence, it is not possible for those marginal nodes to give rise to demand dependencies; dependencies can instead be generated by the other end node of the traffic demand, unless that is also a marginal node.

We make similar investigations for the Wray village wireless mesh network [START_REF] Ishmael | Deploying Rural Community Wireless Mesh Networks[END_REF] composed of 9 nodes, set up by Lancaster For D close to maximum, F(G W ray , D, SP ) still does not achieve 50% (Figure 2(a)). We observe in Figure 2(a), first, that F(G W ray , D, SP ) is bounded to 50% and, second, that the rate of increase is lower than for the previous network.

Looking closely at the Wray topology, we notice that the proportion of marginal nodes is more than three times higher than in the Rice TFA network. This reinforces our previous explanation on the impact of marginal nodes on collaboration. It also appears to outweigh the impact of the network topology density: since the Wray topology is actually much sparser than the Rice topology and results in more overlapping flows, one would expect more demand dependencies.

We now turn to assessing the achievable cooperation for synthetic network topologies. We first use geometric random graphs with 40 nodes spread randomly on a 1000m × 1000m square area, with radio ranges set to 175, 225 and 275m. Figure 2(b) plots F(G GRG , D, SP ) for each of these ranges. An increased transmission range decreases the number of marginal nodes and decreases the expected route length, resulting in a decreasing probability of encountering a non-cooperative node.

This gives better chances, even to demands with a marginal end node, to find useful dependencies. For each radio range, results are shown for one geometric random graph, but we obtain similar results for other instances of geometric random graphs.

Eventually, we consider four topologies without marginal nodes, which we will also use in Section V for the evaluation of our optimized routing approach. These are three geometric random graph topologies (with 16 nodes spread randomly over a 1000m × 1000m area and radio ranges of 300m, 400m and 500m, respectively) and a 4 × 4 grid topology (i.e., 16 nodes).

We observe that a similar asymptotic behavior is obtained even without marginal nodes (Figure 2(c)). We conclude that marginal nodes are not solely responsible for this asymptotic behavior. The explanation is that the increased average node degree, resulting from the increasing transmission ranges, leads to shorter routes. Since a lower number of relays is required, the cooperation increases. However, it also leads to an increased number of possible paths for each demand (i.e., many shortest-path with same weight), thus decreasing the probability that routes will intersect in a way that leads to a better connected G dep (S). It is reasonable to believe that the interplay of these two factors ultimately dictates the level of achieved collaboration. We plan to examine analytically the effect of connectivity graph density and node degree distribution in future work.

IV. COOPERATION-FRIENDLY ROUTING AS AN OPTIMIZATION PROBLEM

Having developed the demand dependency model in Section II as the starting point, we now look into cooperationfriendly routing as a mixed integer optimization problem (MIP). The objective is to maximize cooperation, even at the expense of reasonable route lengths, in a way that satisfies most demands and increases the overall network throughput.

The optimization problem formulations presented in the next paragraph minimize the aggregate route length, maximize the routable throughput (both while enforcing full cooperation) or maximize cooperation even in the presence of marginal nodes.

A. A First Model of Full Collaboration

For routing purposes we define

G d = (V, E d )
, where E d is the set of arcs obtained by the bidirection of every edge in E. For each routing solution, we have a directed dependency graph G dep (S) = (K, A). a first approach to the problem, we aim to find S such that G dep (S) is complete (fully meshed). To model this problem as MIP, we define the following variables: the binary routing variable r k ij ∈ {0, 1} is equal to 1 iff the demand k is routed on the edge {i, j} ∈ E from i to j (in other words, the arc (i, j) belongs to the uniquely selected path from s k to t k ). Similarly, the binary variable y k i ∈ {0, 1} is equal to 1 iff the node i also belongs to the same path. The problem we consider can be modeled as follows:

i∈V -(ℓ) r k iℓ - j∈V + (ℓ) r k ℓj = 0, k ∈ K, ℓ ∈ V k (1) j∈V + (s k ) r k s k j = 1, k ∈ K (2) i∈V -(t k ) r k it k = 1, k ∈ K (3) j∈V + (ℓ) r k ℓj = y k ℓ , k ∈ K, ℓ ∈ V k (4) i∈V -(ℓ) r k iℓ = y k ℓ , k ∈ K, ℓ ∈ V k (5)
y k s k = y k t k = 1, k ∈ K (6)
y k s k ′ + y k t k ′ ≥ 1, k, k ′ ∈ K (7) r k ij , y k i ∈ {0, 1}, (i, j) ∈ E d , k ∈ K (8) for all k, k ′ ∈ K, ℓ ∈ V k , (i, j) ∈ E d , where V -(ℓ) = {i ∈ V : (i, ℓ) ∈ E d }, V + (ℓ) = {j ∈ V : (ℓ, j) ∈ E d }, V k = V \ {s k , t k }.
The constraints (1), ( 2), (3) build a valid path between s k and t k for each k ∈ K. Constraints (4), ( 5) relate the variables defining the paths with arcs with the variables defining the paths with nodes. Constraints (6) simply enforce the use of origin and destination nodes in each demands path. Finally, constraints [START_REF]FICO Xpress[END_REF] are the main design variables imposing that the route for demand k should be routed through the origin or the destination of demand k ′ (or both). To discriminate among a potentially large number of solutions, we include an objective function aiming at global route length reduction:

min a∈E d k∈K r k a (9)
If one wishes to impose specific path lengths restrictions on certain (or all) paths, the following additional constraints should be included in the model:

a∈E d r k a ≤ L k , k ∈ K (10)
where L k is the imposed upper bound on the length of chosen path p k . Note that this model is the most restrictive. It imposes direct dependencies between all demands, which may result in long routes.

B. Eliminating Model Limitations

We now relax the restrictive requirement for completeness of G dep (S). To obtain a strongly connected G dep (S), in line with Proposition 2.2, we introduce additional variables x kk ′ ∈ {0, 1}, x kk ′ = 1 iff (k, k ′ ) ∈ A. These new variables are linked to the previous ones by the following constraints:

x kk ′ ≥ y k s k ′ , k, k ′ ∈ K (11) x kk ′ ≥ y k t k ′ , k, k ′ ∈ K (12) x kk ′ ≤ y k s k ′ + y k t k ′ , k, k ′ ∈ K (13)
They state that demand k is routed over the origin or the

destination of demand k ′ iff (k, k ′ ) ∈ A.
To enforce the strong connectivity of the dependency graph G dep (S), we require this graph to contain at least one arc in each set δ + (Z) (outgoing dependencies from demands in Z) and δ -(Z) (dependencies pointing to demands in Z) for each non-empty set Z ⊂ K:

a∈δ + (Z) x a ≥ 1, Z ⊂ K, Z = ∅ (14) a∈δ -(Z) x a ≥ 1, Z ⊂ K, Z = ∅ (15)
Of course, there is an exponential number of such constraints, but violated connectivity constraints are separated in polyno-mial time and iteratively introduced in the model.

Observe that the objective tends to limit the length of paths whereas the strong connectedness of G dep (S) on the other hand, tends to increase the length of certain paths. As a result, the optimization can return routes, which are not simple any more and contain cycles separated from the actual established route. To remove such unwanted cycles, it is necessary to introduce additional constraints. Assuming that at a given step the optimal routing for demand k ∈ K contains a cycle in the subset X ⊂ V of vertices, X ∩ {s k , t k } = ∅, the following constraint remove cycles routed on each of the vertices of X:

a∈A(X) r k a ≤ |X| -1, X ⊂ V (16)
where A(X) ⊆ E d is the subset of arcs induced by X. Note that again there is an exponential number of such constraints, but the violated ones can be separated in polynomial time.

Full collaboration can also result if G dep (S) is partitioned into strongly connected components without dependencies between them (necessary and sufficient condition from Proposition 2.2). Our optimization achieves strongly connected G dep (S), where possible, i.e., a stronger (sufficient) condition that may result in slightly longer routes. Therefore, running the associated MIP optimization returns an upper bound of total route length. We plan to investigate the applicability of this model at local level in future work.

C. Adding Capacities to the Model

The optimization presented in Section IV-B only requires that flows are functional. This means that an arbitrarily chosen route will be able to transport data, abstracting away throughput requirements that demands may have. While the objective of minimizing overall route length is useful, we are in fact interested in maximizing the throughput of flows in the network, while preserving fairness as much as possible.

To address this issue, we are using a modified version of this optimization, based on the MCF (Maximum Concurrent Flow) model.

We consider fixed throughput demands d k > 0, (∀)k ∈ K and edge capacities C e , (∀)e ∈ E for each ratio link. Given the edge capacities, demand throughputs, and the requirement that the chosen routes S should create a strongly connected G dep (S), it may be that the network is not able to support the requested throughputs. We therefore set our objective as determining the maximum fraction λ ∈ [0, 1] such that λ × d k units of each demand can be routed in the graph without exceeding any edge capacity, while observing the constraints mentioned above. The following constraints need to be added in consideration of this fact:

λ × k∈K d k × (r k ij + r k ji ) ≤ C e , (∀)e ∈ E ( 17
)
where i and j are the two ends of edge e. In implementation, in order to shorten the computation time, we use the following equivalent constraint where we minimize µ:

k∈K d k × (r k ij + r k ji ) ≤ µC e , (∀)e ∈ E (18)
Finally, our problem can be completely modelled by the following: max {λ : (1), ( 2), ( 3), ( 4), ( 5), ( 6), ( 11), ( 12), ( 13), ( 14), ( 15), ( 16), (17)}.

D. Maximizing the Number of Functional Demands

Sometimes it is not possible to achieve a solution where all the demands are functional. This happens for instance when both ends of a flow are assigned to marginal nodes.

For connectivity graphs G where these situations arise, the model in Section IV-B is not able to maximize the number of functional demands and returns no solution, since it requires that all of them are functional. To make our model robust to such cases, it is necessary to introduce additional variables t k ∈ {0, 1}, (∀)k ∈ K, where t k is 1 if demand k is functional and 0 otherwise. Equations ( 2), (3), [START_REF] Ishmael | Deploying Rural Community Wireless Mesh Networks[END_REF] have to be modified accordingly:

j∈V + (s k ) r k s k j = t k , k ∈ K (19) i∈V -(t k ) r k it k = t k , k ∈ K (20)
y k s k = y k t k = t k , k ∈ K (21)
for every k ∈ K. The objective is also adjusted and aims at maximizing the number of functional routes:

max k∈K t k (22)
Once completed, a preliminary optimization run provides us with the set of demands that cannot be routed. However, route lengths are not being minimized by this model. It is therefore necessary to run afterwards the optimization presented in Section IV-B on the same connectivity graph, but by removing the unroutable demands from the initial demand set. By

V. NUMERICAL RESULTS

This section presents results from the previous optimization models on various networks. The aim is to offer an assessment of how well is the shortest path approach behaving and what are the performance tradeoffs introduced by our cooperation criterion. The results have been obtained using FICO Xpress

Optimization Suite [START_REF]FICO Xpress[END_REF].

A. Route Stretch

We now show representative numerical results for the optimization problem formulated in Section IV-B. The objective therein was the minimization of aggregate route length, while achieving full cooperation. Better cooperation implies on average longer paths and we therefore study the tradeoff between path lengths and cooperation on selected topologies.

For low demands/nodes ratio D, F(G, D, SP ) tends to be also small, regardless of the actual topology G and that is why our study focuses on low demands/nodes ratios. All the provided figures are averaged over 100 random multi-hop demands, such that every node is either source or destination (but not both) for exactly one demand.

We first choose a 4 × 4 grid topology with 8 demands. The average cooperation ratio reaches 65% without optimization, which is quite high when compared to complete random assignments. This can be attributed to the absence of inactive and marginal nodes. The average route length for each demand, whether the simulation links it to a functional route or not, is 3.05; it becomes 2.91, if measured only for functional paths.

Table I shows that, as expected, the longer routes are less likely to be functional.

By applying the optimization on the same set of randomly generated demands, the average route length increases to 4.88. Therefore, an increase by a factor of at most 1.67 (for functional routes) is required to raise the cooperation ratio from 65% to 100%. Quite intuitively, for demand profiles with poor cooperation, the paths need to be lengthened more to obtain full cooperation and vice-versa.

We then consider the same random geometric connected topologies without marginal nodes from Section III. For radio ranges of 300, 400 and 500, the cooperation ratios are 37%, 35.5% and 45.25%, respectively, under shortest path routing. The edges/nodes ratios for these graphs are 1.93, 3.43 and 3.06, respectively.

The average route lengths of functional demands for the three networks are 2.51, 2.03 and 2.24, respectively. In order to achieve full cooperation, the average paths need to be lengthened to at most, 5.61, 4.72 and 4.67, respectively. This means an increase by a factor of at most 2.23, 2.32 and 2.08 in the average path length of the networks.

B. Impact of Cooperation on Demand Throughputs

Our model for optimizing cooperation increases route lengths and is therefore expected to reduce the demands' throughputs. This is in fact the price that has to be paid in exchange for full cooperation in the network. Based on the model proposed in Section IV-C, we now evaluate the performance penalty stemming from our cooperation-maximizing approach.

There are two factors which contribute to a drop in performance, namely: i) increase in intra-flow and inter-flow interference and ii) partially overlapping routes. Since evaluating factors in i) goes outside the scope of the current exploration, we study solely the influence of overlapping routes. For this, we use a 4 × 4 grid topology as before, with 8 randomly selected demands whose end nodes are always distinct, such that a node is either source or destination for exactly one demand. We assign a capacity of 10 units to all edges, and set the throughput of all the 8 demands to 1, 2 and 4 units, analyzing for each case λ (over 15 random demand placements). The reason for choosing these values for demand throughputs is that routes will be anyway affected by intra-flow interference and, since the large majority of them will have anyway a route length of at least three hops, the throughput cannot exceed 10 3 in any case for these routes. Running the optimization presented in Section IV-C, we obtain λ = 1 for all the optimization rounds where demand throughputs were set to 1 and 2, which means that the entire traffic can be routed without performance penalties in these cases. In other words, the network is able to transport the data as requested, under the stated assumptions. When the demand throughput is set to 4, in 40% of the cases we obtain λ = 0.83, while for the remaining 60% λ = 1. This means that in 40% of the cases, the throughputs set by demands cannot be sustained by the network and that each of them is to be reduced by approximately 17%. It also implies that the edge with the maximum number of overlapping routes (number denoted by N max ) is crossed by 2 demands in 60% of the cases (N max = 2) and 3 demands in 40% of the cases (N max = 3). It is only after setting demand throughputs to 6 that λ remains below 1 for all the random rounds. By analyzing the data, we obtain that for most of the demand placements N max = 2, while for a smaller fraction of cases N max = 3. These results point to fact that demand overlapping remains moderate.

C. Wray Topology: Maximizing the Number of Functional Demands

As we have seen previously, the cooperation on the Wray topology is relatively low (smaller number of functional demands relative to other topologies), when we use shortest path routing. This happens partly because this topology is similar to a tree, containing a single cycle and a larger number of marginal nodes. Our exploration will be using the optimization model presented in Section IV-D, which minimizes the number of non-functional demands. We aim at understanding how far from optimal were the simulation results based on shortestpath routing and, in general, what is the improvement that the aforementioned optimization model can achieve, thereby characterizing how much cooperation are networks of this type able to support.

We let demands/nodes ratio D vary between 1 3 and 1, while observing the resulting cooperation ratio F(G W ray , D, S o ), where S o is the route placement policy resulting from our optimization model. For each D, 100 random demand placements are created and the corresponding optimization is run.

Therefore, the results presented in Figure 3 are the average of 100 random rounds. When the optimized and unoptimized results (Figure 2(a)) are compared, it can be noticed that the optimized routing offers a much better cooperation ratio, but the improvement tends to be smaller as more and more demands are added to the network. It can be concluded that shortest path routing keeps cooperation to low levels when applied to sparse topologies, such as Wray.

VI. CONCLUSION AND FUTURE WORK

In our work, we extend the study of Felegyhazi et al. [START_REF] Felegyhazi | Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks[END_REF],

where authors argue that cooperation in wireless mesh networks remains low unless an incentive scheme is introduced (using, for instance, virtual currencies). Nevertheless, by taking a different approach we elaborate on a number of questions associated with the assessment of the level of achievable cooperation when monetary incentives are not present.

As a first contribution, we formalize the implicit dependencies among network nodes, generated by given route profiles and traffic matrices. We have derived a graph theoretic criterion for identifying the sets of mutually collaborating nodes, which we have then used in assessing the achievable collaboration for both synthetic (lattice and geometric random graphs) and real-world WMN topologies (Rice TFA, Wray village) under shortest-path routing. We first address the question of how much collaboration can emerge in the network when incentive schemes are absent and how is it affected by the network topology, routing policy, and traffic demand matrix. Our results show that uniformly spread, higher density traffic fosters cooperation. Yet, the achievable cooperation is ultimately bounded by the routing policy and topological characteristics (marginal nodes, node degree distribution).

In the second part we analyze the problem in a more constructive manner, by examining the question of how could the achieved cooperation be improved. In this work, we have realized this by modifying the routing policy such that cooperation is maximized. We first propose an optimization method for obtaining a minimal length route profile that achieves full cooperation, where possible. We then extend this model to account for unroutable demands and present an optimization model based on MCF which shows that although routes are longer when full cooperation is obtained, their overlapping remains within reasonable limits.

Numerical results for cooperation-friendly routing policies emphasize a number of related tradeoffs. In particular, to compensate for the selfishness of some nodes, the routes need to be lengthened. Moreover, routes are less disjoint and contention on network resources increases. In this paper we have only analyzed the route overlap, but assessing the additional interference introduced by the cooperation criterion is also very relevant to this exploration. We therefore plan to incorporate interference in our models, which would then give a complete image of the tradeoffs involved. One way to achieve this would be by extending problem formulations in Section IV while drawing on previous studies regarding interference [START_REF] Jain | Impact of interference on multi-hop wireless network performance[END_REF]. Future work will also investigate analytically dynamic demand profiles, where demand profiles may vary over time, and consider the requirements that arise when adding throughput constraints.

Finally, on a more practical level, we would like to address the problem of a distributed algorithm appropriate for cooperation-maximizing routing.

Fig. 1 .

 1 Fig. 1. Constructing the dependency graph for a topology, a set of demands and the corresponding routes

  Fig. 2. Cooperation curves for various mesh topologies as a function of D

Fig. 3 .

 3 Fig. 3. Cooperation curves for the Wray village topology

TABLE I FRACTION

 I OF FUNCTIONAL DEMANDS FOR EACH ROUTE LENGTH -4 × 4

		GRID NETWORK
	Route length Fraction functional demands
	2	0.72
	3	0.66
	4	0.60
	5	0.48
	6	0.14
	modifying our initial model we obtain an optimization that
	maximizes the number of functional demands, while keeping
	the associated routes' size at a minimum.

ACKNOWLEDGMENT

The work presented in this paper is supported by the European Commission, under Grant No. FP7-224619 (the ResumeNet project).


Andrés Ferragut

José García

Fernando Paganini

Network utility maximization for overcoming inefficiency in multirate wireless networks

Wireless local area networks, in particular the ones based in the IEEE 802.11 standard, are nowadays used around the world to deliver Internet access, and are becoming increasingly prevalent. One of the crucial performance issues that these networks introduce is the possibility of having multiple transmission rates in the physical layer.

In this paper, we use the Network Utility Maximization framework to characterize the cross-layer interaction between the transport protocols such as TCP and the underlying MAC level rate adaptation. We describe the resource allocation imposed by current wireless networks in this framework, and characterize its equilibrium. Moreover, we propose alternative resource allocations that overcome the inefficiencies found in current protocols, and show simple mechanisms to impose more efficient equilibria in single cell scenarios. We also present simulations of these mechanisms in action, and discuss further generalizations to more complex networks.

I. INTRODUCTION

The Network Utility Maximization (NUM) framework originating in the work of Kelly [START_REF] Kelly | Rate control in communication networks: shadow prices, proportional fairness and stability[END_REF], has been extensively applied in recent years for cross-layer optimization in wireless networks, (see [START_REF] Chiang | Layering as optimization decomposition: A mathematical theory of network architectures[END_REF], [START_REF] Lin | A tutorial on cross-layer optimization in wireless networks[END_REF] and references therein). We can roughly classify this literature in terms of the multiple access technology considered. For the case of a scheduled MAC, the cross-layer optimization can be tackled through a dual decomposition approach, although the scheduling component is difficult. In the case of a random MAC, much of the effort has gone into modelling collisions; while this leads to nonconvexities (see [START_REF] Chiang | Layering as optimization decomposition: A mathematical theory of network architectures[END_REF]), recent results [START_REF] Jiang | A distributed CSMA algorithm for throughput and utility maximization in wireless networks[END_REF], [START_REF] Proutière | Throughput of random access without message passing[END_REF] have shown how to cast the problem in appropriate variables to approach the performance of the scheduled case.

We argue, however, that when considering wireless LAN technologies that are now prevalent in the world, the emphasis on collisions is misplaced. In recent versions of the IEEE 802.11 [START_REF]Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF] wireless LAN standard, the loss of performance due to collisions is not as important as one might expect, due to two main reasons: on one hand, most of the traffic is downlink, and the Access Point (AP) does not collide with itself; secondly, with the 802.11 default parameters, collision probabilities and resolution time are low when compared with data transmission, whenever the number of stations is not too large. These conclusions follow from detailed models of the IEEE 802.11 Distributed Coordination Function (DCF), pioneered by [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]. Other aspects of the technology have a much larger impact, in particular the adaptation of physical layer modulation rates (ARF [START_REF] Kamerman | Wavelan-II: a high performance wireless lan for the unlicensed band[END_REF]), as studied recently in [START_REF] Kumar | New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs[END_REF]. Understanding cross-layer issues in this context is the main focus of this paper.

We begin in Section II by analyzing the effective rates the TCP layer can achieve when operating above a wireless MAC layer, specifically 802.11. This provides us with a characterization of the data rates offered by the MAC layer to the TCP layer, which is the basis for the rest of the analysis.

Secondly, in Section III we analyze the joint effect of using TCP above the multiple rates offered by the MAC layer. A first contribution of this paper is to pose this problem in the NUM framework, by taking into account the TCP behavior and the losses incurred in the AP buffer, in a single cell scenario. In our model, we exhibit the inefficiency that results from this arrangement, where users with high PHY rates are severely penalized, with minimal benefit for the slow users. This generalizes previous results ( [START_REF] Kumar | New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs[END_REF]) to fully take into account the TCP behavior.

In a second step in the analysis, we interpret the behavior in terms of a NUM problem with a natural constraint, but where the user utilities are inversely scaled with capacity. Based on this model, in Section IV we find ways of removing this bias, in particular we find a suitable price scaling that achieves global convergence to the unbiased NUM problem. We also explore ways to implement price scaling at a packet level, and we develop a new algorithm based on an appropriate Active Queue Management scheme. In Section V we present extensions of the analysis to a general network, involving possibly wired and wireless links. In Section VI we exhibit the performance of the proposed algorithms through simulations. Conclusions are given in Section VII.

II. IMPACT OF OVERHEADS IN TCP OVER 802.11.

The purpose of this section is to quantify the impact of protocol overheads when using TCP over 802.11. Using 802.11 implies that, when transmitting a packet of length L and due to the use of the Distributed Coordination Function, the Access Point (AP) must comply with a series of backoff and waiting times, as well as headers included by the PHY layer.

This means that the MAC layer offers a service to the upper layer consisting of a tranmission rate C i P HY i . This has been analyzed before [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF], [START_REF] Kumar | New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs[END_REF], [START_REF] Ferragut | A connection level model of IEEE 802.11 cells[END_REF] and we will recall and extend this analysis here.

The time it takes to send this packet has a fixed component given by

T 0 i := DIF S + H + L P HY i + SIF S + M AC ACK i , (1)
that includes the time in the air and all overheads, plus a random number of time slots Kσ, where K ∼ U {0, . . . , CW }.

In Table I we show typical values of these parameters for 802.11g. We are interested in the average rate obtained by a station to study the upper layer effective rate. Observing that each packet is treated independently, the transmission times of successive packets form a renewal process, and the renewal reward theorem [START_REF] Feller | An Introduction to Probability Theory and Its Applications[END_REF] tells us that in the long range the average rate is:

C 0 i = L EKσ + T 0 i = L CWmin 2 σ + T 0 i , (2)
where we substituted K for its mean. We also took CW = CW min since we are modeling downlink traffic from the AP, which does not collide with itself. We also assume the appropriate P HY i has been used so that one can neglect packet transmission errors. The denominator of the preceding expression (mean total time) is denoted by T i .

In Table II we show the corresponding MAC level rates C 0 i for the different P HY rates allowed in 802.11g with parameters as in Table I. Note the impact of overheads in the highest modulation rates.

When TCP connections are taken into account, another overhead must be considered: the TCP ACK packet. These packets were designed to have low impact on the reverse path, by having a length of 40 bytes. However, due to the overheads added by the MAC layer, the TCP ACK becomes non negligible, in particular at high modulation speeds. We assume that one TCP ACK is sent in the uplink direction for every TCP packet sent downlink. We will also assume that collision probabilities are low between downlink packets and the TCP ACKs. Under these assumptions, the TCP ACK packet introduces another overhead time in the system. The effective data rate then becomes:

C i = L T i + T CP ACK i (3)
where T CP ACK i is the average time to transmit a T CP ACK packet and is given by:

T CP ACK i := DIF S+H+ L ack P HY i +SIF S+M AC ACK i , (4)
where L ack is typically 40 bytes. These effective data rates C i are also shown in Table II In the following, we shall not address the impact of overheads and consider them given, since they are included in the standards. We can thus, for the purpose of modelling, concentrate in the C i 's, which are the effective data rates at which packets from a TCP connection are served. In the following section we will model the behavior of the TCP connections above this MAC layer.

III. TCP RESOURCE ALLOCATION IN A MULTIRATE WIRELESS ENVIRONMENT

Let us consider first a single cell scenario where N users indexed by i = 1, . . . , N are downloading data from a single AP.

Assume that each station establishes a downlink TCP connection, with sending rate x i . Packets of these connections will be queued in the interface queue of the AP, before being put into the shared medium to reach their destination. We want to calculate the effective output rate y i attained by each user. Assume that the Head of Line (HOL) probability for a packet of user i is proportional to the input rates x i . Then, through a renewal reward argument similar to [START_REF] Kumar | New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs[END_REF] we have:

y i = p HOL,i L j p HOL,j L/C j = x i j x j /C j (5)
which is similar to eq. ( 5) of [START_REF] Kumar | New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs[END_REF], but without the collision terms.

To complete the loop, we must now model the TCP behavior, that determines the input rates x i . Recall (c.f. [START_REF] Srikant | The Mathematics of Internet Congestion Control[END_REF]) that TCP Reno-like algorithms can be modelled as a primal controller:

ẋi = k(x i )(U ′ i (x i ) -p i )
where U (x) is an increasing and concave Utility function, p i is the link loss rate (interpreted as a price) and k(x i ) > 0 a scaling factor. In the analysis, we will restrict ourselves to the α-fair family of utility functions introduced in [START_REF] Mo | Fair end-to-end window based congestion control[END_REF], which verify U ′ (x) = Kx -α with α > 0 a parameter which determines the compromise between efficiency and fairness of the allocation. We can model the link loss rate as:

p i = x i -y i x i + = 1 - 1 j x j /C j + = p
which is simply the proportion of packets that exceed the current service rate, where (•) + = max(•, 0) as usual. With this model the packet loss rate of each flow is the same and the complete dynamics follow:

ẋi = k(x i )(U ′ i (x i ) -p), (6a)
p = 1 - 1 j x j /C j + . ( 6b
)
We would like to characterize the equilibrium of this dynamics in terms of a NUM problem. For this purpose, consider the following function:

Φ(x) = i x i C i -1 -log i x i C i , whenever i xi Ci > 1 and 0 otherwise. Lemma 1: Φ is a convex function of x.
Proof: Φ(x) can be written as

Φ(x) = g(f (x)) where f (x) = i x i /C i is a linear function of x and g(u) = (u - 1 -log(u))1 {u>1}
, where 1 represents the indicator function. It is easy to see that, for u > 0, g ′ (u) = max{0, 1 -1/u} which is nonnegative and increasing function of u. Therefore, g is increasing and convex and thus Φ is convex [START_REF] Boyd | Convex Optimization[END_REF].

Consider now the following convex optimization problem: Problem 1:

max x i 1 C i U i (x i ) -Φ(x) (7)
We have the following: Theorem 2: The equilibrium of the dynamics ( 6) is the unique optimum of Problem 1.

Let V (x) denote the objective function in equation [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]. The proof of the Theorem depends on the following lemma for V (x), proved in the Appendix:

Lemma 3: The upper level sets of V , {x : V (x) γ} are compact and cover the positive orthant as γ → -∞.

Proof of Theorem 2: By Lemma 3 and the concavity of the objective function, there is a unique optimum for Problem 1, and it must satisfy the optimality conditions, namely:

1 C i U ′ i (x i ) - ∂ ∂x i Φ(x) = 0 ∀i
By substituting Φ we have:

1 C i   U ′ i (x i ) -1 - 1 j x j /C j +   = 0
Identifying the last term as p = p(x) in ( 6), the optimality conditions become: [START_REF]Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF].

U ′ i (x i ) -p = 0 ∀i which is the equilibrium condition of
Theorem 4: The equilibrium of the dynamics ( 6) is globally asymptotically stable.

Proof: Consider V (x) as a Lyapunov function of the system. Differentiating along trajectories:

V = ∇V • ẋ = i k(x i ) C i (U ′ i (x i ) -p) 2 0
So V is increasing along the trajectories. Moreover, V = 0 only when x = x * the solution of Problem 1. Therefore, the upper level sets of V are forward invariant and since by Lemma 3, they cover the positive orthant, this equilibrium is globally asymptotically stable. The function Φ in Problem 1 plays the role of a penalty function, and thus Problem 1 can be sen as an approximation of the following problem:

Problem 2 (Modified Network Problem):

max x i 1 C i U i (x i )
subject to the constraint:

i x i C i 1
which is the equivalent to the Network problem of [START_REF] Kelly | Rate control in communication networks: shadow prices, proportional fairness and stability[END_REF], with two variants. The first one is that the constraint is rewritten in terms of x i /C i , the "time proportion" the shared medium is used by connection i. The sum of the allocated time proportions must be less than one and this is a natural constraint 1 .

The second main difference with [START_REF] Kelly | Rate control in communication networks: shadow prices, proportional fairness and stability[END_REF] is the scaling factor C i for the user utility. This implies a negative bias to users with higher rates, since they would have less weight in the net utility. This bias leads to a radical equalization of rates to approximately the one of the slowest station, a well known effect in 802.11 environments (c.f. [START_REF] Kumar | New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs[END_REF]).

Remark 1: In the case where all users share a common utility function (e.g. equal RTT TCP/Reno connections), the solution of problem Problem 2 reduces to

x * i = 1 j 1/C j ,
which is the harmonic mean of the data rates. This is in accordance with [START_REF] Kumar | New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs[END_REF] where this rate is obtained as an upper bound on the realistic rate permanent connections experiment, and collisions are considered. As compared with [START_REF] Kumar | New insights from a fixed-point analysis of single cell IEEE 802.11 WLANs[END_REF], in our result the behavior of TCP is fully taken into account. As we mentioned before, we are disregarding collisions in the downlink traffic, and focusing on the issue of the multiple rates. Moreover, note that this result is independent of the TCP flavor in use, so the MAC layer is actually determining the allocation.

Example 1: To see the biasing effect of Problem 2 consider the following example. Assume 3 users are downloading data from a single AP, and they have common utilities U (x) = -1 τ 2 x which model the TCP/Reno response, while their MAC layer rates are C i = 10. In this case x * i = 3.333 for all three users. If user 3 for instance changes its radio conditions to C 3 = 1, the new allocation results:

x * 1 = x * 2 =
x * 3 = 0.8333. Note that the fastest destinations are heavily penalized due to the user 3 inefficiency 2 .

Remark 2: We can analyze the system also from a connection-level perspective. If connections of rate C i are not permanent but they arrive as a Poisson Process of intensity λ i and have exponentially distributed workloads, in the case where all the utilities are the same, the system becomes a Discriminatory Processor Sharing queue [START_REF] Altman | A survey on discriminatory processor sharing[END_REF]. In particular, jobs with effective rate C i have weight 1/C i . This has been noted before in [START_REF] Ferragut | A connection level model of IEEE 802.11 cells[END_REF], [START_REF] Bonald | Flow-level stability of utility-based allocation in non-convex rate regions[END_REF]. The results of this section therefore generalize these previous results to the case where the utility functions are not equal for each connection. Note that in this case the queue is not a DPS queue anymore.

The previous remarks and examples suggest that ways to remove the bias in Problem 2 must be explored. In the following sections we propose alternative resource allocations for the single cell networks.

IV. A MORE EFFICIENT RESOURCE ALLOCATION FOR A SINGLE CELL

Based on the preceding discussion, it would seem natural to remove the bias in Problem 2 by considering:

Problem 3 (Wireless Network Problem):

max x i U i (x i )
subject to the constraint:

i x i C i 1,
Observe that the constraint here is similar to the ones discussed in [START_REF] Lin | A tutorial on cross-layer optimization in wireless networks[END_REF], where the schedulable region of the system is defined in terms of the convex hull of the transmission rates. The purpose of this section is to analyze how to achieve the solution of Problem 3 without resorting to a complicated scheduling mechanism in the AP.

To see the difference with Problem 2, consider the following interesting property:

Proposition 5: If U (x) = K log(x) for all connections, then the equilibrium of Problem 3 is x * i = C i /n. In particular, the allocated rate for user i depends only on its own effective rate and the total number of users. 2 The result from Problem 1 would be x * 1 = x * 2 = x * 3 = 0.89, which shows that the barrier function approximation is very close. This shows that imposing proportional fairness between users protects the fastest users from the lower rate ones. For instance, in Example 1, high rate users would be unaffected by the change in C 3 . When TCP Reno is in use, we do not have such protection but the situation is nevertheless better, as the following example shows.

Example 2: Assume we have the same situation of Example 1. When all three users have C i = 10, the equilibirium of Problem 3 is the same as before, x * i = 3.33. When user 3 changes its radio conditions and C i = 1, the equilibrium changes to x * 1 = x * 2 = 1.93, x * 3 = 0.61. We see then that in this case we can increase total network throughput by ≈ 80% with respect to Example 1, and fastest users are not as heavily penalized.

We would like to drive the network to the equilibrium of Problem 3. For this purpose, consider the Lagrangian:

L(x, p) = i U i (x i ) -p i x i C i -1 .
A simple primal-dual gradient algorithm to solve this optimization problem is:

ẋi = k(x i ) U ′ (x i ) - p C i , (8a) ṗ
= i x i C i -1 + p , (8b)
where k(x i ) > 0 as before and (•) + p is the usual positive projection. It is well known [START_REF] Arrow | Studies in Linear and Nonlinear Programming[END_REF], [START_REF] Feijer | Krasovskii's method in the stability of network control[END_REF] that the trajectories of the dynamics given by (8) converge globally to the optimum of Problem 3.

In the wired case, dual algorithms have interpreted the price variable as the queueing delay [START_REF] Low | Optimization flow control, I: basic algorithm and convergence[END_REF], [START_REF] Low | Internet congestion control[END_REF]. This is also the case here in this modified version. By integrating ṗ we see that p tracks the amount of time the shared medium is not capable of coping with the demands, and thus accumulating as delay in the queue.

More formally, let b i denote the amount of data of connection i in the buffer (assume it is non empty). Then ḃi = x iy i and the delay d is given by:

d = i b i C i .
Therefore, recalling equation ( 5) we have:

ḋ = i ḃi C i = i x i C i -1.
Observe further that when all capacities are equal C i = C we recover the delay based model of [START_REF] Low | Optimization flow control, I: basic algorithm and convergence[END_REF], [START_REF] Low | Internet congestion control[END_REF].

From equations [START_REF] Kamerman | Wavelan-II: a high performance wireless lan for the unlicensed band[END_REF] we see that in order to appropriately solve Problem 3, we need to scale the price to which the user reacts by the effective rate C i . This makes sense since connections with higher rates use the medium more efficiently, and thus should be charged less whenever this resource is scarce. Note however that this poses problems on implementation, because it prevents from using directly the queueing delay as the price. Moreover, the user endpoint has to be notified of the correct MAC level rate, which is infeasible.

A. The Multirate RED algorithm

In order to drive the system to the optimum of Problem 3, we propose to use a simple Active Queue Management policy which we call the Multirate RED algorithm (MRED).

Instead of using queueing delay as the price, we propose to use as a proxy the buffer length b, and to generate the price, the AP discards packets randomly with probability p i proportional to b

Ci for connection i. This gives a linear Random Early Detection (RED) algorithm, but with probabilities related to the effective data rates. Note that less packets will be dropped for connections with higher MAC rates. Moreover, this mechanism can be implemented in the AP resorting only to local information, such as destination address and current rate for this destination.

The closed loop dynamics for the proposed system is:

ẋi = k(x i ) (U ′ (x i ) -κb/C i ) , (9a) ḃ
= i x i -y i + b = i y i i x i C i -1 + b . (9b)
where κ > 0 is the proportionality constant of RED. These equations are similar to [START_REF] Kamerman | Wavelan-II: a high performance wireless lan for the unlicensed band[END_REF]. In particular, in equilibrium, the x i and p = κb will satisfy the KKT conditions of Problem 3. Stability results for these equations are harder to obtain, in Section VI we explore its behavior by simulation.

V. EXTENSION TO GENERAL NETWORK TOPOLOGY

In this section, we will discuss how to extend the previous analysis to the case where multirate wireless links and wired ones are present in the system. The main purpose of this section is to find a common price for the different type of network capacity constraints to which users should react in order to allocate resources properly. We identify three classes of capacity constraints:

• The classical wired constraints, i x i c.

• The wireless multirate constraints, i xi ci

1.

• The contention between cells constraints: j α j 1, where α j is the proportion of time each contending node is using the shared medium. Consider then a network of J nodes, j = 1, . . . , J, connected by links l = 1, . . . , L. These links can be wired or wireless, and have an effective transmission rate c l . In the case of wired links, c l is the link capacity. In the wireless case, it is the effecive data rate. Let i = 1, . . . , n represent the connections, with rate x i , and R the classical routing matrix: R li = 1 if connection i traverses link l and 0 otherwise.

To represent the contention inherent to the wireless medium, we group the links l in contention sets: two links belong to the same contention set if they cannot be transmitting simultaneously and define G kl = 1 if link l belongs to contention set k and 0 otherwise; we call G the contention matrix.

The network capacity constraints can then be written as Hx 1 where H is given by H = GC -1 R, with G, R previously defined, C = diag(c l ) and 1 a column vector of ones.

To see how this framework enables us to model different situations, consider the following examples:

Example 3 (Wired network): If all links are wired, the contention matrix G is the Identity matrix. By taking R and C as before we recover the classical wired constraints i∈l x i c l .

Example 4 (Single wireless cell): If there is only one wireless AP with N users in the cell, we can take R as the identity matrix, C as the wireless effective capacities and G = 1 T (there is only one contention region where all links participate). We then recover the constraints discussed in Section IV.

Example 5 (Wireless Distribution System): To see a more complete example, consider the network composed of wired and wireless links shown in Figure 1. This topology appears in outdoor wireless distribution scenarios. We can model the capacity constraints of this network with the above framework by taking:

G =     1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1     C = diag(c, c AP1 , c AP2 , c 1 , c 2 , c 3 , c 4 ) R =           1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1           AP1 AP2 Backhaul Access (C) c AP1 c AP2 c 1 c 2 c 3 c 4
Fig. 1. Topology of a mixed wired-wireless distribution system with 4 endusers.

We can now pose the general Network Utility Maximization problem, which is:

Problem 4 (Wired-Wireless Network Problem):

max x i U i (x i ) subjecto to: Hx 1.
The previous problem seeks an optimal allocation within the natural constraints of the network, expressed in terms of allocated time. These constraints are equivalent to the ones used in the scheduling literature [START_REF] Lin | A tutorial on cross-layer optimization in wireless networks[END_REF]. However, modelling the constraints as time proportions leads to a natural way to control the input rates of the sources without explicit scheduling for each destination in the nodes. something that is difficult to implement and requires significant message passing between them. In out approach, we assume that the buffers are served as FIFO and we control the input rates to the network to obtain a suitable time sharing.

Consider now the Lagrangian of Problem 4:

L(x, p) = i U i (x i ) -p T (Hx -1) (10)
where p = (p 1 , . . . , p K ) T is the vector of prices. We see therefore that we have one price for each contention graph. By denoting q = H T p, the KKT conditions of Problem 4 are U ′ i (x i ) = q i where q i is given by:

q i = l:i∈l k:l∈k p k c l (11)
Therefore, the connection must react to a price which is the sum of the prices of the the contention graphs it traverses, divided by the corresponding link capacities. Again, to solve Problem 4, we can use a primal-dual algorithm which gives the following dynamics:

ẋi = k(x i ) (U ′ (x i ) -q i ) (12a) ṗ = (Hx -1) + p , (12b)
q = H T p. (12c)
These dynamics are globally asymptotically stable [START_REF] Arrow | Studies in Linear and Nonlinear Programming[END_REF], [START_REF] Feijer | Krasovskii's method in the stability of network control[END_REF] and its equilibrium is the solution of Problem 4. In this context, the prices track again the queueing delays at each node. The remaining issue is whether this prices can be correctly generated and transmitted to the sources via the MRED implementation discussed in Section IV-A. Characterizing the topologies where decentralization is possible is, at the time of writing, ongoing work. However, we will present now two important examples in which this mechanism can be applied.

Example 6 (Mixed wired-wireless access network): A typical configuration for wireless access coverage is to distribute access points in non overlapping channels across the region to cover, and wire them to the Internet access node. This produces the tree topology of Figure 2. There, the APs are connected to a central switch, which is also connected to the router handling the Internet connection. End users are then connected to the APs via 802.11 for example. In this case, each user traverses three contention graphs, one per link. Assuming the link capacities and user distributions shown in Figure 2, the corresponding price for user i is calculated according to equation 11 as:

q i = p access c access + p dist c dist + p APi c i
where p access , p dist and p APi are the queueing delays suffered by the data packets of user i along the network, scaled by the corresponding link capacities. By using the Multirate RED algorithm in each link in the network, we can therefore transmit this price to the source, and impose the notion of fairness of Problem 4 by emulating the dynamics of [START_REF] Srikant | The Mathematics of Internet Congestion Control[END_REF]. We shall show that this mechanism indeed works in Section VI.

Example 7 (Wireless distribution system): A variation of the above example occurs when the area to cover is large, for instance, large outdoor deployements. In this case, the distribution links that connect each AP with the wired network are replaced by a wireless cell that backhauls all the APs and which is directly connected to the Internet router, as in Figure 1. The APs have 2 radio interfaces: one to connect to the backhaul link and one for local connectivity.

In this case, the corresponding price for user i can again be calculated according to 11 as:

q i = p access c access + p BH c APi + p APi c i
where now p BH reflects the queueing delay in the backhaul node, and c APi is the MAC layer rate at which the AP of user i connect to the backhaul node. Again, by using Multirate RED in this tree topology we can impose the notion of fairness of Problem 4.

VI. IMPLEMENTATION AND SIMULATIONS

As we discussed in section IV, the price to which a TCP connection should react in order to attain the equilibrium of Problem 3 is the queueing delay. However, this price should be scaled by the effective data rate C i the connection experiments in each link. Clearly, this is difficult to implement without resorting to scheduling. Moreover, typical TCP connections use loss based congestion control mechanims, such as TCP Reno. Therefore, we propose to use the MRED algorithm developed in Section IV-A at each node to attain the optimum of Problem 3.

To test the proposal in a real environment, we implemented this algorithm in the Network Simulator ns-2 [START_REF]The Network Simulator NS-2[END_REF]. Our implementation is based on the library dei80211mr [START_REF]dei80211mr: a new implementation of 802[END_REF]. Two important extensions were made to the library: the existing ARF mechanism was updated to cope with the possibility of a single node having different modulation rates for different destinations, which reflects the real behavior of current APs. The second modification was to implement the Multirate RED (MRED) queue, where the described early packet discard takes place.

Note that the cross-layer information needed for implementation of the mechanism is minimal: whenever a packet for next-hop j is received, it is discarded with probability p j = κb/C j where κ acts as a scaling parameter, b is the current queue length, and C j is the corresponding effective rate for the current modulation rate the AP maintains with destination i (as in Table II). In the case of wired links, the link capacity is used to scale this drop probability. The nondropped packets are served then on a FIFO basis.

We now present several simulation scenarios to illustrate the behavior of the proposed algorithm.

A. Single-cell scenario

We simulate the topology shown in Figure 3, which consists of a single cell 802.11g scenario in which 3 users are connected with a modulation rate P HY i = 54M bps, and some time later, a fourth user is added at the lowest possible modulation P HY 5 = 6M bps. All four connections use TCP/Newreno and share equal Round Trip Times (RTTs), then having similar utility functions. For these modulation rates, the effective data rates according to Table II are C i ≈ 22.4M bps, i = 1, 2, 3 and C 4 ≈ 5.1M bps. In the first graph of Figure 4, we see that all connections converge to the same throughput, which is approximately x * = 3.0M bps, the harmonic mean discussed in Remark 1. In the second graph, we show the behavior of the system under the MRED algorithm. In this case the allocation converges approximately to x * i = 4.2M bps, i = 1, 2, 3 and x * 4 = 2.1M bps, which is the exact solution of Problem 3. Note that the total throughput in the network is increased by more than 20%.

B. Wired-wireless scenario

The purpose of this example is to show that Problem 2 captures the behavior of the system when the TCP connections have different RTTs, and thus different utilities, and to show how efficiency can also be improved in this case with the MRED algorithm.

We consider the topology of Figure 5, where two connections with different RTTs share a wireless bottleneck link. In this example, connection 1 has twice the RTT of connection 2, and its station is closer to the AP, having a modulation rate P HY 1 = 54M bps. The second connection has a modulation Plugging these values into Problem 2 using the effective data rates of Table II, the allocation results x * 1 = 2.25M bps and x * 2 = 4.5M bps. In the first graph of Figure 6 we show the results of the corresponding simulation, which shows that indeed the connection throughputs converge approximately to the values predicted by Problem 2.

By using MRED in the AP we can change the allocation to the one proposed in Problem 3, removing the bias of Problem 2. The resulting allocation is x * 1 ≈ x * 2 ≈ 4.1M bps. In the second graph of 6 we show the corresponding simulation results. We see that the MRED algorithm approximately drives the system to the new equilibrium. Note that this new equilibrium is ≈ 20% more efficient than the preceding one.

C. Tree topology

In this example, we simulate the topology of Figure 2 with two distribution APs and two users in each AP. The access link capacity is c access = 20M bps representing a typical access capacity. The distribution links have c dist = 100M bps and thus are overprovisioned. The wireless cells are identical and have each one two users, with modulation rates P HY 1 = P HY 3 = 54M bps and P HY 2 = P HY 4 = 6M bps. Each user has a single TCP connection and all connections have equal RTTs.

Plugging these values in Problem 3 gives the following allocation:

x * 1 = x * 3 = 6.5M bps x * 2 = x * 4 = 3.5M bps By using the MRED algorithm as discussed in Section V, we can drive the system to this allocation. Results are shown in Figure 7, where we see that the throughputs appoximately converge to the above equilibrium.

VII. CONCLUSIONS

Throughout this paper, we applied the Network Utility Maximization framework to characterize the cross-layer interaction between the TCP transport protocol with an underlying MAC where multiple modulation rates coexist. This situation is present in typical IEEE 802.11 deployment scenarios. We analyzed the impact of overheads in the throughput of TCP connections, and then we described the resource allocation imposed by current wireless networks in this framework, characterizing its equilibrium through a suitable NUM problem.

In the second part of the paper, we proposed an alternative resource allocation that generalized the fairness and efficiency notions of TCP in wired networks to this context. This new resource allocation overcomes the inefficiencies found in current protocols. We also showed a simple mechanism to impose these more efficient equilibria in single cell scenarios and also showed possible generalizations of this procedure to more complex topologies. Finally we validated the results by simulations that show that the proposed algorithm indeed drives the system to the desired allocations.

In future work, we plan to extend the proposed mechanisms to the new 802.11 additions, where these issues may become more important due to the higher data rates involved, and due to packet aggregation mechanisms.

APPENDIX

Proof of Lemma 3: Denote by V (x) = i 1 Ci U i (x i ) -Φ(x) the objective function of Problem 1. We analyze the case 0 < α < 1, where we have the following bound:

i 1 C i U i (x i ) = i K i x 1-α i C i (1 -α) = i K i C -α i 1 -α x i C i 1-α K max i x i C i 1-α K i x i C i 1-α .
Here K = max i { KiC -α i 1-α }. Let y = i x i /C i and assume y > 1. Using the previous bound we have: V (x) Ky 1-αy + 1 + log(y) = h(y) and since α > 0, the function h(y) → -∞ when y → ∞ so for any given γ we can find y γ such that g(y) < γ for all y > y γ . Therefore, for all x ∈ E γ = { i x i /C i > y γ } we have that V (x) < γ. This proves that the level sets of V , {V γ}, are contained in the complement of the set E γ , which is compact. Since γ is arbitrary, we also have that V (x) → -∞ when ||x|| → ∞.

The case with α = 1 can be proven analogously. For α > 1, the utilities are upper bounded and Φ(x) → ∞ whenever ||x|| → ∞ so the result is trivial.

Fig. 2 .

 2 Fig. 2. Topology of a mixed wired-wireless access network.

Fig. 3 .

 3 Fig. 3. Topology of a single-cell scenario.

Fig. 4 .

 4 Fig. 4. Comparison between throughputs: without MRED (above), with MRED (below).

Fig. 5 .

 5 Fig. 5. Wired-wireless topology.

Fig. 6 .

 6 Fig.6.Wired-wireless topology simulation. Above: original allocation. Below: MRED algorithm.

Fig. 7 .

 7 Fig. 7. Throughputs of TCP connections for a wireless access scenario with 4 users. MRED is in use.

  . Note the strong impact of the TCP ACKs in the performance of the protocol, particurlarly at high modulation rates.

	PHY rates	MAC rates (C 0 i )	Eff. data rate (C i )
	54	31.9	22.4
	48	29.7	21.2
	36	24.6	18.5
	24	18.4	14.6
	18	14.6	12.1
	12	10.4	8.9
	6	5.57	5.08
		TABLE II
	MAC RATES FOR THE CORRESPONDING PHY RATES OF 802.11G IN
		MBPS. L = 1500 BYTES.

This set can also be interpreted as the convex hull of the rates obtained by assigning all capacity to each of the nodes, which is equivalent to models used in scheduled networks[START_REF] Lin | A tutorial on cross-layer optimization in wireless networks[END_REF].

ACKNOWLEDGMENTS

This work was partially supported by LATU/Ceibal, CSIC I+D (Universidad de la República), ANII-FCE and AFOSR-US.