Vincenzo Mancuso

Omer Gurewitz

Ahmed Khattab

Edward W Knightly

Elastic Rate Limiting for Spatially Biased Wireless Mesh Networks

IEEE 802.11-based mesh networks can yield a throughput distribution among nodes that is spatially biased, with traffic originating from nodes that directly communicate with the gateway obtaining higher throughput than all other upstream traffic. In particular, if single-hop nodes fully utilize the gateway's resources, all other nodes communicating with the same gateway will attain very little (if any) throughput.

In this paper, we show that it is sufficient to rate limit the single-hop nodes in order to give transmission opportunities to all other nodes. Based on this observation, we develop a new rate limiting scheme for 802.11 mesh networks, which counters the spatial bias effect and does not require, in principle, any control overhead.

Our rate control mechanism is based on three key techniques. First, we exploit the system's inherent priority nature and control the throughput of the spatially disadvantaged nodes by only controlling the transmission rate of the spatially advantaged nodes. Namely, the single-hop nodes collectively behave as a proxy controller for multi-hop nodes in order to achieve the desired bandwidth distribution. Second, we devise a rate limiting scheme that enforces a utilization threshold for advantaged single-hop traffic and guarantees a small portion of the gateway resources for the disadvantaged multi-hop traffic. We infer demand for multi-hop flow bandwidth whenever gateway resource usage exceeds this threshold, and subsequently reduce the rates of the spatially advantaged single-hop nodes. Third, since the more bandwidth the spatially disadvantaged nodes attain, the easier they can signal their demands, we allow the bandwidth unavailable for the advantaged nodes to be elastic, i.e., the more the disadvantaged flows use the gateway resources, the higher the utilization threshold is.

We develop an analytical model to study a system characterized by such priority, dynamic utilization thresholds, and control by proxy. Moreover, we use simulations to evaluate the proposed elastic rate limiting technique.

I. INTRODUCTION

A key challenge for rate control in IEEE 802.11 mesh networks is that the total traffic originating from any node that is directly connected to a gateway forms a high-priority aggregate flow when competing with other traffic. That is, for gateway-destined traffic, traffic originating from multihop nodes is disadvantaged and can only use resources not demanded by advantaged gateway-connected nodes.

In this paper, we develop a new elastic rate control method for mesh networks with three key techniques. First, we exploit and indeed require the distributed priority property that derives from MAC layer behavior. Because the low priority traffic obtains only resources not utilized by the high priority traffic, a rate control system only needs to control the high priority traffic in order to control the throughput of both classes. Thus, we design a rate control method in which the single-hop nodes collectively behave as a proxy controller for multihop nodes: single-hop (advantaged) nodes allow multi-hop (disadvantaged) nodes to increase their rate by decreasing their own aggregate rate. Likewise, single-hop nodes can force multi-hop nodes to decrease their rate by increasing their own rate.

Second, we address a critical problem in the priority system: how can single-hop nodes allocate resources on behalf of multi-hop nodes without knowing their demands? That is, while a particular single-hop node is in range of a small number of multi-hop nodes, it is out of range of many others; without knowing if multi-hop nodes are even backlogged, how can a single-hop node make rate control decisions on their behalf? Moreover, multi-hop nodes cannot simply make use of additive increase when their demand increases, as they can only increase their throughput if single-hop nodes decrease their aggregate rate. To tackle these issues, we propose a distributed mechanism that operates a Gateway Airtime Partitioning (GAP), in which a small portion of the gateway airtime is reserved for multi-hop nodes to signal their demand (signaling bandwidth), whilst all nodes have open access to the remaining gateway airtime.

Third, the amount of signaling bandwidth determines the capability of multi-hop nodes to signal their demand and the time needed for the rate control mechanism to converge to a new stable state after the traffic demand changes. However, the higher the multi-hop traffic, the lower the additional demand that multi-hop nodes are expected/allowed to request, and, in turn, the less signaling bandwidth is needed. Hence, when multi-hop traffic is high, we allow the signaling bandwidth to be used for multi-hop data traffic, i.e., we elastically reduce the signaling bandwidth as a function of the multi-hop offered load.

Thus, we design our rate control algorithm as follows: (i) single-hop nodes are aware of the status of the gateway airtime utilization, i.e., they can estimate or get notified whether the gateway utilization is above a predefined threshold; (ii) singlehop nodes agree that the aggregate traffic originating from all single-hop nodes should never exceed a particular utilization threshold; (iii) thus, if the utilization threshold is exceeded, it is due to multi-hop traffic; (iv) we interpret crossing the utilization threshold as a request for a multi-hop flow to be in the additive increase mode.

With steps (i)-(iv), each (advantaged) single-hop node has a means to infer whether the (disadvantaged) multi-hop nodes want to increase their rates. With this view of the state of both classes of nodes, single-hop nodes can set their own rates according to rate control objectives, and, because of the priority nature of the system, they have also set the rates of the multi-hop flows.

We develop a simple fluid model to isolate and study the aforementioned system properties of priority, utilization thresholds, and control by proxy. We use the model both as a means to precisely define these properties and to show that our rate control scheme is able to converge to a desired operating point in this simplified priority system.

Finally, we present an extensive set of ns-2 simulation experiments to evaluate the performance of the proposed scheme in more realistic settings than the fluid model. Our results show that our approach achieves targeted rates similar to those of a scheme that has perfect knowledge of all offered loads and rate limits flows according to their ideal rates. Moreover, we show that the very limited computational overhead of our approach yields significant gains compared to techniques that use rate control messages such as the IEEE 802.11s [START_REF] Camp | The IEEE 802.11s extended service set mesh networking standard[END_REF].

The rest of the paper is organized as follows. In Sections II and III we define the network model and the key system's properties, respectively. We propose our rate control framework, GAP, in Section IV. We model the system's properties and analyze our rate control scheme in Section V. In Section VI, we evaluate the performance of the proposed scheme. We overview related work in Section VII, and conclude the paper in Section VIII.

II. NETWORK MODEL

We consider non-mobile multi-hop wireless networks that forward traffic to and from gateway nodes. The physical topology of the mesh networks does not need to show any particular structure. In contrast, the forwarding topology yields a set of trees rooted in gateway nodes. Thus, we consider networks with unconstrained physical topology, which embed a forwarding tree of degree N ≥ 1 and depth D ≥ 2 per gateway. In particular, we focus on a single-gateway mesh, in which a routing protocol establishes a set of forwarding links yielding a tree structure. Note that since the gateway capacity is of the order of few tens of Mbps, due to the 802.11 maximum transmission rate, typical values of D are 2 to 3, and N ≤ 10 to ensure sufficient per-node resources.

For a particular tree, mesh nodes other than the gateway node can be classified into two sets: a set S of nodes that can directly connect to the gateway, and a set M which includes the remaining nodes. Fig. 1 depicts an example of data forwarding tree network topology. Note that the physical interconnection is not a tree in the example.

For the sake of simplicity we consider wireless nodes equipped with a single half-duplex radio. Nodes in the two sets S and M compete for gateway access through a shared wireless interface. However, our approach can be easily extended to multiple-radio nodes. In fact, it would suffice to logically decompose the network into groups of wireless transceivers, each group using a single 802.11 channel, and apply our analysis to each group separately.

We assume that no peer-to-peer traffic is allowed within the mesh, i.e., all non-gateway nodes can open connections GW set set Fig. 1. A possible network topology. Solid and dotted lines represent dataforwarding and non-data-forwarding links, respectively. Data-forwarding links form a tree which is rooted in the gateway node.

with the gateway or with remote Internet nodes only. Since we are only interested in those performance factors that are originating in the mesh network, we do not consider the effects of the connection path between the gateway and any other remote Internet node. Hence, for the sake of simplicity, we model all downstream flows as originating at the gateway, and all upstream flows as terminating at the gateway node. However, in the rest of the paper we focus on the performance of upstream flows only. This assumption is motivated by the fact that previous work already showed that downstream traffic impairments do not arise in case of UDP, and TCP performs very similarly both upstream and downstream [START_REF] Shi | Measurement and Modeling of the Origins of Starvation in Congestion Controlled Mesh Networks[END_REF].

Hence we look at the upstream gateway capacity as a fixed bandwidth and define the upstream gateway airtime utilization, U (t), as the amount of time the gateway transceiver is active or deferring due to other data transmissions within its carrier sense range. The time the gateway spends in idle state or counting down its backoff counter represents unutilized gateway airtime. All nodes are assumed to be using the same rate for data packet transmissions, thus gateway airtime utilization is equivalent to the consumed bandwidth.

Finally, we refer to flow i as the aggregate traffic originating from node i (i.e., flow i includes all upstream flows originated by node i, but does not include traffic forwarded on behalf of other nodes). We denote by R i (t) the rate at which node i throttles flow i at time t.

III. CHARACTERIZING 802.11 FORWARDING TREES

In this section, we identify three fundamental properties of 802.11 mesh networks that affect our rate control design.

A. Distributed Approximate Priority Property

A number of studies have described the uneven distribution of bandwidth among flows in multi-hop wireless networks (e.g., [START_REF] Garetto | Modeling media access in embedded two-flow topologies of multi-hop wireless networks[END_REF], [START_REF] Garetto | Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks[END_REF], [START_REF] Qiu | A general model of wireless interference[END_REF]). Specifically, due to spatial bias some flows can capture more resources than others. In wireless mesh networks, the spatial orientation of flows going to and from the gateway can further exacerbate severe throughput imbalances, giving higher bandwidth to nodes that are closer to the gateway. In particular, the most advantaged nodes are the ones directly connected to the gateway (one hop away from it), hence whenever nodes in the single-hop and multi-hop node sets compete for accessing the tagged gateway interface, the distributed traffic originating at all nodes in the singlehop set S is of almost-strict priority in accessing the gateway resources compared to the traffic originating at nodes in M. Thus, the traffic originating at any member of the multi-hop set M can only access the residual gateway resources not used by all nodes of the single-hop set S. Hence, if the combined demands of all nodes in the single-hop node set S consume all of the available gateway resources, the traffic originating at any multi-hop node in M will not be able to access the gateway resources. We refer to such a system as a distributed approximate priority system wherein the distributed load of the sets S and M are the high priority and the low priority traffic entities, respectively.

In order to demonstrate the distributed approximate priority system we performed an experiment using mesh nodes running LocustWorld open-source mesh networking software. Each mesh node is equipped with a single SMC 2532-b IEEE 802.11b wireless interface operating at the 2.4 GHz ISM band with maximum transmission power of 24 dBm. The physical layer rate is set to 11 Mbps. We use such nodes to realize the network topology shown in Fig. 2(a) in an indoor environment. We use iperf to generate traffic at source nodes. The duration of each experiment run is 120 seconds. In the experiment we gradually increase the offered load of node S 2 from 128 Kbps up to 6 Mbps in 512 Kbps steps. The multi-hop node M 1 carries backlogged traffic. Node S 1 does not offer any traffic and just forwards node M 1 's traffic. Fig. 3 depicts the throughput of each flow as well as the gateway utilization versus the single-hop node's offered load, both for UDP and TCP traffic. The single-hop node's received throughput is almost equal to its demands regardless of whether the two-hop node's offered load is backlogged. Thus, the single-hop node's traffic has almost-strict priority in accessing the gateway resources (a perfect strict priority system would yield the Y = X dashed line until saturation). Meanwhile, the two-hop node's traffic can only partially utilize the gateway airtime that is not utilized by the single-hop node's traffic. 1 When both flows are continuously backlogged, the single-hop traffic utilizes almost all of the gateway airtime, thereby starving the two-hop node. When we added a threehop node to the two-hop branch (not shown here), we observed similar behavior. Note that the transmissions of the two-hop nodes in M include both the locally generated and forwarded traffic. Thus, when the two-hop nodes are of approximate low priority in accessing the gateway, all the multi-hop traffic is of approximate low priority when competing with singlehop traffic. We repeat similar experiments using the ns-2 simulator with the default 802.11 parameters on a broader set of topologies such as the topology depicted in Fig. 2(b). The 1 Gateway utilization drops when both flows share the gateway due to time spent in contention, collisions, and collision resolution. results show similar trend as the one presented in Fig. 3, i.e., the existence of almost-strict priority in accessing the gateway airtime for single-hop traffic, whenever competing with a twohop node. These results are presented in [START_REF] Khattab | Overheadfree congestion control framework for IEEE 802.11 multi-hop mesh networks[END_REF].

The two other properties which inspire our flexible rate control mechanism, relate to congestion around the gateway.

B. Gateway Airtime Saturation Property

The second property asserts that, assuming all links transmit at the same rate, a congested link in a single gateway topology (possibly a few hops away from the gateway) indicates congestion around the gateway (e.g., gateway airtime must be saturated). The reasoning is that since we assume that all traffic is going to and from the gateway, the congested link traffic also originates or terminates in the gateway. Hence, either the traffic traversing the congested link propagates all the way to the gateway, which implies congestion around the gateway, or the traffic cannot propagate all the way to the gateway due to some other congested region closer to the gateway. Extending the same argument will let us conclude that the congestion is localized in the vicinity of the gateway.

C. Proxy Control Property

The third property, which relates to the first two, asserts that enforcing free airtime in the extended gateway neighborhood will give nodes in set M some transmission opportunities. Therefore, the single-hop nodes can act as a distributed proxy which controls the transmission opportunities of multi-hop nodes.

The reasoning for this property is based on the spatial reuse property in multi-hop topologies, i.e., nodes two and three hops away from the gateway can utilize the free gateway airtime to get some channel access, given that the singlehop nodes left same gateway airtime unused. Nodes four hops away from gateway can transmit simultaneously with singlehop nodes, which force two-hop nodes to backoff, and, in turn, provide four-hop nodes with transmission opportunities. This spatial reuse argument can be extended to nodes which are further away from the gateway. Obviously, since hidden nodes cannot coordinate their channel access, distance from the gateway is in inverse proportion to successful transmission opportunities.

IV. GAP: GATEWAY AIRTIME PARTITIONING THROUGH

ELASTIC RATE LIMITING We now introduce an elastic rate limiting strategy for singlehop nodes, that exploits the network characteristics presented in Section III. The proposed strategy is named Gateway Airtime Partitioning (GAP) since it yields an airtime partition between gateway resources that can always be used by any node and resources that should be reserved for multi-hop demand indication.

A. GAP Framework

According to their unique system characteristics identified in Section III, we pose the rate control problem in 802.11 multi-hop trees as by which means to achieve an arbitrary bandwidth distribution between the two spatially biased node sets S and M, given their time-varying demand. GAP rate control objective is to ensure minimum rates that would be guaranteed under saturation load conditions, and to fairly share unused resources among all competing nodes. The distinct nature of our rate control problem comes from the approximate priority property of the spatially advantaged node set S that allows its distributed demands to be almost fully served, irrespective of the demands of the spatially disadvantaged node set M. The demands of the disadvantaged multi-hop nodes can only utilize the gateway airtime that is not used by the advantaged node set S.

Our new rate control approach is to have the set of singlehop nodes collectively behave as a proxy controller for multihop nodes. Thus, the main challenge in GAP is how can singlehop nodes allocate resources on behalf of multi-hop nodes without knowing their demands. Nodes in S should neither leave gateway resources more than the demands of nodes in M nor less than M's minimum guaranteed rate. Moreover, nodes in S can neither infer the demands nor observe the throughput of all nodes in M due to the distributed nature of the network, and since we do not flood the network with per-node control messages.

Our GAP framework is based on two fundamental ideas. First, we have all nodes in the spatially advantaged node set agreeing that the combined gateway airtime utilization of their locally generated traffic, not including forwarded traffic, is limited to a particular threshold, rather than the entire gateway airtime. Consequently, spatially disadvantaged nodes' traffic can always use the residual gateway airtime for successful data transmissions (either from a two-hop node in M to a node in S, or a node in S forwarding a multi-hop packet to the gateway). Since all nodes in S are aware that their traffic's should not exceed a predefined threshold, nodes in S interpret the excess gateway airtime utilization as only due to transmissions of multi-hop traffic. Hence, the only piece of information that nodes in S need is whether the gateway airtime utilization exceeded the threshold. This information might be encoded into a 1-bit message that is high when the traffic threshold is exceeded, and otherwise is low. This message might be sent from the gateway to all nodes in S, e.g., by encoding the bit into a currently unused subtype value in the Frame Control field of the 802.11 ACK, or by including a traffic indicator field in beacons regularly transmitted by the gateway, or also by allowing the gateway to transmit a new type of management frame, newly defined for traffic indication. Another way to obtain the same information on the gateway airtime utilization might consist in letting single-hop nodes estimate the gateway activity by overhearing gateway's ACKs. This approach is in principle possible at single-hop nodes, but is particularly prone to estimation errors due to frame collisions and failures in decoding some ACKs, e.g., due to variations in the SNR, not all single-hop nodes might be able to decode gateway's ACKs transmitted at the highest modulation rate. In both ways, explicitly or implicitly, each single-hop node obtains a gateway utilization indicator I U , whose binary value is high if the bandwidth reserved for multihop traffic is in use.

We define the disadvantaged-flow Signaling Bandwidth, B D = γU * , γ << 1, as a small portion of the system's resources that nodes in S collaboratively agree not to use for the transmission of their locally generated traffic to the gateway. Instead, this bandwidth will be used exclusively by the set of spatially disadvantaged flows. Any flow originating at a node in M will use this bandwidth to transmit data, thereby, expressing that its current demands would like more bandwidth, if possible, to the spatially advantaged node set S. Consequently, the distributed single-hop proxy controller will have all nodes in S collaboratively adapting their rates to realize the rate control objective.

The second part of the GAP framework is to prevent the spatially disadvantaged flows from misusing B D to get more than their minimum guaranteed rate if backlogged. In fact, if we would allow the single-hop nodes to unboundedly reduce their rates as long as B D is partially of fully utilized, backlogged multi-hop nodes could use B D to exclusively capture the system's resources, irrespective of the system's approximate priority behavior. Thus, we design GAP to not allow nodes in S to reduce their rates if their gateway utilization does not exceed a minimum guaranteed rate.

The Minimum Guaranteed Single-hop Rate, U * S , is defined as the minimum bandwidth to be guaranteed for the node set S under saturation load conditions achieving a specific distribution of the gateway airtime (e.g., max-min fairness, proportional fairness, etc.). U * S is the sum of the minimum guaranteed rates, F i , of single-hop nodes. Likewise, U * M is defined as the minimum airtime guaranteed for M under saturation loads. The sum of U * S and U * M is the saturation gateway bandwidth U * . These values are apriori computed by means of analytical models (e.g., [START_REF] Gambiroza | End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks[END_REF]) refined by measurements.

Note that adopting a minimum guaranteed rate for nodes in S, not only prevents disadvantaged flows from misusing B D , but also allows to tune the bandwidth effectively reserved for signaling according to the utilization of nodes in M. In fact, as nodes in M receive more bandwidth, less bandwidth is needed to indicate unserved demands. Thus, even though in a heavily utilized network the maximum unutilized bandwidth is B D , the actual unutilized bandwidth can be reduced as soon as more disadvantaged demands are served. The U * S minimum guarantee is the tool that we use to allow the signaling bandwidth to be partially used by data flows originating at M. For instance, at saturated load conditions, all of the system's resources are fully utilized and both traffic types will receive their guaranteed rates-i.e., nodes in S will receive their minimum guaranteed rate U * S , while modes in M will take all the rest-and no bandwidth is left for additional signaling. In general, the single-hop nodes are allowed to exploit a bandwidth that ranges from U * S to (1 -γ)U * , the actual limit being dynamically and automatically determined by the demands of the multi-hop nodes, i.e., ideally:

R S = (1 -γ)U * -λ M , λ M ∈ [0, U * M -B D ] ; U * S , λ M > U * M -B D ; (1)
where λ M is the aggregate demand of nodes in M, and R S is the maximum aggregate rate allowed for nodes in S, which is a piecewise linear function of λ M . The corresponding unutilized part of the signaling bandwidth, under fully backlogged nodes in S, ideally ranges between 0 and B D :

B free D = B D , λ M ∈ [0, U * M -B D ] ; max(0, U * M -λ M ), λ M > U * M -B D . (2)
In order to ensure that the single-hop set receive U * S under saturation loads, γ can be at most

U * -U * S U * .
However, γ should be much less than

U * -U * S U *
in order to allow single-hop nodes to explore gateway resources more than U * S .

B. Distributed Algorithm

Here we present the algorithmic details of our distributed rate control scheme. When using GAP, all nodes in S locally limit their transmission rates R i (t) based on the gateway utilization U (t) and the local single-hop throughput. Algorithm 1 implements the proposed GAP framework at each singlehop node in S for Additive Increase Multiplicative Decrease (AIMD) rate adaptation model. The algorithm is invoked every time a node in S updates its gateway utilization indicator I U , indicating whether or not U (t) > (1 -γ)U * .

Algorithm 1

Input:

IU : Gateway Utilization Indicator Ti(t) : Throughput of Node i ∈ S λi(t) : Instantaneous Offered Load of Node i ∈ S Fi : Minimum Guaranteed Rate of Node i Output:

Ri(t): The Rate Limit of Node i ∈ S

Upon update of IU Do 1: if ((Ti(t) < Fi(t) IU == low) && Ti(t) < λi(t)) 2: Ri(t) = Ri(t -) + α 3: else if (Ti(t) > Fi(t) && IU == high) 4: Ri(t) = Ri(t -) * β, 0 < β < 1
The GAP framework is implemented via two thresholds, namely, the maximum allowable single-hop utilization (1γ)U * , and the minimum guaranteed single-hop rate U * S = i F i . γ is a positive fraction that defines how much of the total gateway utilization U * is allowed for disadvantaged flows' demand indication. If the maximum allowable singlehop utilization is not exceeded, all nodes in S should have I U set to low; otherwise, they all should have I U set to high.

The distributed rate control process implemented at each node in S is driven by the values of I U and the achieved throughput: if the gateway airtime utilization is below the threshold (1 -γ)U * or the node throughput is below F i , and the node demand is not satisfied, a single-hop node linearly increases its rate by α. On the other hand, when the gateway airtime utilization is above the (1 -γ)U * threshold, a singlehop node multiplicatively reduces its rate by a factor β only if its throughput exceeds its minimum guaranteed rate F i . Thus, only nodes that are currently receiving more than their fair shares will reduce their rates upon traffic overflow indication.

U(t) (t) (t) U * SP q (t) q (t) U(t) R (t) (t) U * SP q (t) q (t) (t) q c (t) (a)
In Section V, we present a simple system model that isolates the main properties of 802.11 tree networks, and uses this model to analyze our rate control approach.

V. ANALYTICAL MODEL

In this section, we present a simple fluid model to isolate and study rate control in a system with priority service, utilization thresholds for inference of an underserved state, and control by proxy for high-priority nodes to control the rates of low-priority nodes. Our model omits all aspects of wireless networks and only focuses on these properties alone.

A. GAP in a Strict Priority System Model

Strict Priority System Model. Our rate control approach is driven by the distributed approximate prioritization of 802.11 mesh networks. We present the simplest system model that formulates this property as a priority fluid server. In particular, we consider a work-conserving queuing system in which two traffic flows are served via a single fluid server with fixed capacity U * . Since our rate control objective is to distribute the system's capacity between the two different aggregate flows (advantaged and disadvantaged), we consider a single infinite capacity buffer per traffic type as shown in the uncontrolled system depicted in Fig. 4(a). Traffic from the buffer for the spatially advantaged node set S has strict priority access to the server: when this buffer is non-empty, it is drained at rate U * . The other buffer enqueues the spatially disadvantaged multihop traffic and is served only when the high priority buffer is empty. We consider a fluid server utilization and arrival processes U S (t), U M (t) and λ S (t), λ M (t), respectively. If no rate control is performed in the system, U S (t) and U M (t) can be written as in [START_REF] Liu | On fluid queueing systems with strict priority[END_REF]:

U S (t) = U * 1 {qS (t)>0} ; (3) U M (t) = [U * -U S (t)] 1 {qM(t)>0} ; (4)
where 1 {expr} is an indicator function which is equal to 1 if the expression expr is true and otherwise is equal to zero. Using equations ( 3) and ( 4), the dynamic equations for the occupancy of the two system buffers are given by

qS (t) = λ S (t) -U * 1 {qS (t)>0} ; (5) qM (t) = λ M (t) -U * (1 -1 {qS (t)>0} )1 {qM(t)>0} . (6)
GAP Rate-Controlled System Model. GAP controls the server utilization of the low priority traffic by controlling the rate by which the high priority traffic accesses the server. Therefore, we add a buffered rate controller, R S (t), at the input of the high priority buffer. Since the GAP distributed rate control process is driven by the knowledge of the gateway utilization, the rate controller R S (t) is able to observe the strict priority server as depicted in Fig. 4(b). On the other hand, the low priority buffer has no knowledge of U (t) due to the spatial disadvantage of the set of nodes it represents. Due to the strict priority nature of the system, the low priority traffic utilization U M (t) is the server capacity not used by the high priority traffic, and eq.( 4) holds also for the case shown in Fig. 4(b). Hence, U M (t) is controlled by controlling U S (t).

Since GAP aims at preventing the high priority traffic from consuming all of the gateway capacity U * , the service rate of the high priority traffic U S (t) will be always equal to the rate limit R S (t) in the fluid system, i.e.,

U S (t) = R S (t)1 {qc(t)>0} (R S (t) ≥ U * S , ∀t ≥ 0) ; (7)
Consequently, the high priority system buffer q S can be always considered empty (i.e., q S (t) = 0, ∀ t ≥ 0) under the fluid approximation of the controlled system. Thus, the queue occupancy dynamic equations of the rate-controlled system are given by

qc (t) = λ S (t) -R S (t)1 {qc(t)>0} ; (8) qM (t) = λ M (t) -[(U * -U S (t)] 1 {qM(t)>0} . (9)

B. Algorithmic Operation

For an AIMD rate adaptation model, the dynamic equation of the high priority buffer controller is given by

ṘS (t) = α1 {U(t)<(1-γ)U * } 1 {RS (t)<λS (t)} + -βR S (t)1 {U(t)>(1-γ)U * } 1 {US (t)>U * S } . ( 10
)
The first term in the right hand side of (10) corresponds to an additive increase in the rate whenever the feedback signal implies U (t) < (1 -γ)U * . Namely, the high priority traffic increases its rate and correspondingly decreases the allocated rate to low priority traffic whenever the server utilization is below the (1 -γ)U * threshold. The constant α is the additive increase step size. The second term in the right hand side of [START_REF] Gerla | TCP over Wireless Multi-hop Protocols: Simulation and Experiments[END_REF] corresponds to multiplicative decrease. The constant β is the multiplicative decrease factor. The high priority buffer controller decreases its rate by β whenever the server utilization exceeds the (1 -γ)U * threshold to allow low priority traffic demands to be served. The dynamic equation for the high priority traffic rate controller [START_REF] Gerla | TCP over Wireless Multi-hop Protocols: Simulation and Experiments[END_REF], along with the queue occupancy dynamics in ( 8) and ( 9), characterizes our rate rate-controlled system.

Based on the offered load, the three following conditions drive the system to a steady state point, i.e., ṘS (t) = 0.

(a) Light high priority traffic demands. If λ S (t) is below the minimum guaranteed single-hop utilization U * S , the strict priority behavior of the system allows the low priority demand λ M to be served up to U * -λ S . In this case, both terms of [START_REF] Gerla | TCP over Wireless Multi-hop Protocols: Simulation and Experiments[END_REF] are equal to zero, λ S = U S ≤ U * S ≤ R S , and λ M ≤ U * -λ S . A full gateway airtime utilization is hence possible.

(b) Unsaturated traffic demands. If the offered load of the high priority buffer exceeds the minimum guaranteed singlehop threshold U * S but it does not exceed the rate limiting value R S , and the aggregate offered load is at most equal to (1γ)U * , there is no need for changes in the rate control, and both terms in [START_REF] Gerla | TCP over Wireless Multi-hop Protocols: Simulation and Experiments[END_REF] are zero (U * S < U S = λ S ≤ R S and U ≤ (1-γ)U * ). From this state, GAP allows the high priority buffer controller to increase its rate until the overall server utilization U (t) reaches the threshold (1-γ)U * , whilst the low priority traffic can express future increments in its demands using B D plus the resources left unused by the high priority flows.

(c) Saturated traffic demands. Finally, consider the case wherein the high and low priority traffic demands are greater or equal to U * S and (1-γ)U * -U * S , respectively. As explained earlier, the low priority traffic will keep using B D = γU * causing the high priority buffer controller to decrease its rate R S until the high priority utilization U S is equal to its minimum guaranteed value U * S . Thus, the system enters a steady state in which U * S = R S = U S ≤ λ S and U ≥ (1 -γ)U * . The low priority utilization is min (λ M (t), U * M ), and thereby a 100% utilization of the server capacity is possible if λ M (t) ≥ U * M , without any losses whatsoever due to any type of overhead.

C. Stability of the Equilibrium Points

Here, we study the stability of GAP described by the nonlinear ordinary differential equation in [START_REF] Gerla | TCP over Wireless Multi-hop Protocols: Simulation and Experiments[END_REF]. More specifically, we examine the stability of linearizations about the equilibrium points. Although such a technique does not lead to sufficient conditions for global stability (i.e., stability under arbitrarily large perturbations), it does lead to necessary conditions and provides useful insights [START_REF] Kumar | Communication Networking: An Analytical Approach[END_REF].

Definition 1: An equilibrium point R eq S is said to be stable if small perturbations from that point decay with time. This condition is met only if the Taylor series expansion of the derivative of the right-hand side of equation [START_REF] Gerla | TCP over Wireless Multi-hop Protocols: Simulation and Experiments[END_REF] at R eq S is negative valued [START_REF] Kumar | Communication Networking: An Analytical Approach[END_REF]. We refer to this condition as the stability criterion.

The following two theorems characterizes the stability of the equilibrium points of GAP.

Theorem 1: The equilibrium points of the proposed rate control framework are satisfying the stability criterion.

Theorem 2: Perturbations of the equilibrium points of the system are exponentially decaying with time with constant that is based on the equilibrium point.

Due to space limitations we only state the theorems. The detailed proofs are available in [START_REF] Khattab | Overheadfree congestion control framework for IEEE 802.11 multi-hop mesh networks[END_REF].

D. Applications of the Model

In [START_REF] Khattab | Overheadfree congestion control framework for IEEE 802.11 multi-hop mesh networks[END_REF] we present some applications of the model. Here, we overview such applications.

In our model we intentionally isolate the main 802.11 network properties driving our rate control approach. However, the model allows for the incorporation of other aspects of 802.11 networks for deeper understanding of the performance of our rate control approach. For example, in [START_REF] Khattab | Overheadfree congestion control framework for IEEE 802.11 multi-hop mesh networks[END_REF] we extend the model to replace the fluid service model with the 802.11 service model presented in [START_REF] Garetto | Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks[END_REF].

We also show how to deduce the values of the additive increase and multiplicative decrease parameters that ensure the stability of the AIMD behavior at the steady state operation points of the algorithm.

VI. PERFORMANCE EVALUATION

In this section, we use simulations to demonstrate that by using elastic rate limiting, the GAP achieves the targeted gateway sharing with close accuracy compared to idealized 802.11s-compliant algorithms, yet GAP incurs very little or no overhead and thus achieves higher utilization.

A. Simulation Setup

Simulations are conducted using the unmodified IEEE 802.11 MAC implementation in ns-2 v.2.31 with default parameters. The carrier sensing range and the transmission range are set to 250m. The auto-rate mechanism is disabled and the data rate of all nodes is set to 11 Mbps. Each node is equipped with a single half duplex interface with an omnidirectional antenna. We disable the RTS/CTS exchange in order to avoid the associated overhead. We use the token bucket filter implementation in ns-2 to implement the rate limiters at the single hop nodes. We do not simulate the gateway utilization estimation scheme, rather, the gateway utilization is made available to each single hop nodes via a centralized estimator employing EWMA filter. We denote x in GAP(x) as the amount of signaling bandwidth B D used in the experiment. At saturation load conditions, we target max-min fair rates for the two sets S and M.

Our benchmark is the Inter-TAP Fairness Algorithm (IFA) [START_REF] Gambiroza | End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks[END_REF] that is an IEEE 802.11s-like link-layer rate control algorithm. In IFA, backhaul nodes periodically broadcast their demands and link capacities to adjacent nodes (every 300 ms) in control messages sent at the base rate (we simulate 50byte packets). Using such information, all nodes individually calculate their fair shares, using the reference fairness model presented in [START_REF] Gambiroza | End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks[END_REF], and communicate them to neighboring nodes in order for the fair share computation in a contention region to be coordinated. We consider an idealized variant of IFA that uses a global observer that measures the individual link capacities needed for the fair rate calculations.

We present results for TCP traffic upload traffic. Other traffic matrices including mixes of UDP and download traffic are available in [START_REF] Khattab | Overheadfree congestion control framework for IEEE 802.11 multi-hop mesh networks[END_REF]. The reported results, except for the instantaneous behavior results, are the average of 10 simulations.

B. Tracking Changes in the Multi-hop Traffic's Demands

In this experiment, we demonstrate the ability of the singlehop node set S to track changes in the offered load of the multi-hop node set M. We consider both a gateway of degree 1 and 4 with two-hop branches. Single-hop nodes carry backlogged traffic. The offered load of the two-hop node set M is initially 1.2 Mbps (higher than the saturation share). Every 30 seconds, we decrease the offered load of the twohop node set M in 300 Kbps steps until it reaches zero, then increase it again starting at 150 seconds with the same step (in the 4-branch topology, we turn off/on a two-hop node every 30 seconds). As shown in Fig. 5, as long as the multi-hop node set M offered load is below its saturation fair share, the single-hop node set S increases its rate for efficient gateway utilization. However, the single-hop traffic cannot utilize the signaling bandwidth (which is 256 Kbps and 512 Kbps in Fig. 5(a) and 5(b), respectively). Consequently, when the offered load of the two-hop nodes increases, nodes in M transmit using B D such that nodes in S infer the change in M's offered load and reduce their rate accordingly. Fig. 5(b) shows that tracking demand changes is doable, even though more challenging, also when multiple single-hop nodes are competing, and the distributed AIMD mechanism generates higher throughput oscillations while keeping almost unchanged the average and the aggregate utilization.

C. Topological Factors

We evaluate the performance of the GAP mechanism and the 802.11s-like algorithm under the impact of topological factors such as the gateway degree, branch depth, and hidden terminals. We use three performance metrics: (i) the accuracy of the received throughput T with respect to the targeted throughput T * , defined through the error

E = 1 2 T S -T * S T * S + T M -T * M T * M ; (11)
(ii) the time to rise t rise , defined as the time needed, for fully backlogged single-hop nodes to reach the maximum allowable gateway utilization upon switching off all the multi-hop load;

(iii) the time to decay t decay , defined as the time needed for fully backlogged single-hop nodes to decrease their aggregate rate to the minimum guaranteed single-hop bandwidth, after switching on fully backlogged multi-hop nodes. t rise and t decay define the convergence time of the selected mechanism. Impact of gateway degree. First, we study the impact of the distributed nature of the network on the performance of both GAP and IFA. To address this issue, we vary the gateway degree N while having all nodes in S in range of each other (in order to isolate hidden terminals effect and utilization estimation accuracy). Fig. 6 depicts the aggregate throughput of the two node sets and the total gateway utilization for gateway of degree of 1 and 8 and two-hop branches. Table I lists the error with respect to the targeted rates and the rise and decay times for these two topologies.

For a single branch topology, GAP closely converges to the targeted rates (with 6.7% error) with a signaling bandwidth as low as B D = 256 Kbps (7.6% of U * ), as shown in the leftmost set of bars in Fig. 6(a). As N increases, the amount of signaling bandwidth needed for the GAP algorithm to accurately converge to the targeted rates increases as depicted in Fig. 6(b). Note that the accuracy and stability of both GAP and IFA algorithms decrease with N . However, only IFA causes the gateway utilization to decrease with N . Such performance degradation of IFA is attributed to the increased overhead of the periodically exchanged control messages. Moreover, GAP converges to the target rate faster than IFA as more nodes cooperate in rate control (Table I). In IFA, nodes need more time to convey the changes in their loads to the gateway to compute the fair rates and communicate the rates back to different nodes.

Impact of branch depth and hidden nodes. Our results presented in [START_REF] Khattab | Overheadfree congestion control framework for IEEE 802.11 multi-hop mesh networks[END_REF] extend the validity of the results presented here to network with more than two hops, and with different degree of coordination between nodes. Our experiments show that the required signaling bandwidth increases with the branch depth, and decreases when nodes in S are not coordinated (i.e., hidden). In fact, the presence of hidden nodes slows down the transmission rates of single-hop nodes, thereby, more transmission opportunities occur for multi-hop nodes. In contrast, the throughput of the IFA system further decreases with both the branch depth and the presence of hidden nodes.

D. Robustness of GAP

The gateway utilization indication can be affected by errors due to the utilization estimation process performed either by the gateway or by each single-hop node independently. In this set of experiment we want to observe the behavior of two single-hop nodes (S 1 and S 2 ) and one two-hop node (M 1 ) (as in Fig. 2(a)), when the gateway's resource estimation process is affected by a random error.

We numerically evaluate Algorithm 1 in a scenario in which all nodes are fully backlogged and single-hop nodes are controlled by the GAP. In particular we compare the results obtained under error-free estimation and under a ±40% uncertainty in each estimation. The parameters for the simulation are scaled to the gateway capacity U * as follows: B D = 0.2U * , U * S = 0.5U * , α = 0.01U * , and β = 0.9.

The error-free case depicted in Fig. 7(a) shows the throughput oscillations typical of an AIMD rate control algorithm. After the warm up phase, i.e., soon after the last flow enters the network, single-hop nodes never go below their guaranteed rate (25% of U * ), and the two-hop node stays close to its fair share (that is 25% after considering that two-hop node throughput consumes about two times the gateway airtime of single-hop throughput). In the error-prone scenario of Fig. 7(b), we can observe larger oscillations in the throughput, as expected due to the large estimation errors. However, the peaks in each throughput curve are quickly recovered by the AIMD mechanism adopted by the GAP. Note that the average throughput of each node remains closer to the selected share rate, i.e., 25% for each node. Therefore, the GAP is shown to be robust to very high estimation errors.

E. Per-node vs. Aggregate Minimum Guarantees

Finally, we investigate the performance of the GAP when only using a per-node minimum guaranteed rate (Fig. 8(a), representing results obtained with Algorithm 1), versus a modified GAP version using an aggregate single-hop minimum guaranteed rate (Fig. 8(b), representing the outcome of an algorithm in which the gateway utilization indication I U is evaluated in conjunction with an aggregate single-hop utilization indication I S , i.e., the binary value I U is replaced by (I U && I S )). As well as for I U (see Sec. IV-A), the value of the indication variable I S can be either estimated by each node or simply notified by the gateway with an extra signaling bit, or also encoded together with I U . In our experiment, we consider a 4-branch topology in which all nodes are initially fully backlogged; then, every 30 seconds, one single-hop node is switched off after the other, until only multi-hop nodes remain active.

As can be seen in Fig. 8, when the offered multi-hop traffic is saturated and the load of the single-hop set is asymmetrically distributed among different nodes in S, the adoption of pernode utilization guarantees can cause the algorithm based only on the maximum single-hop allowable utilization to fail realizing the targeted gateway sharing objective between the two sets S and M, but it conservatively advantages the multihop node set whilst not starving the single-hop node set. This is because the backlogged demand of M keeps the signaling bandwidth fully utilized, and thereby, nodes in S cannot increase their rates above their individual minimum guaranteed rate.

VII. RELATED WORK

There have been significant research efforts investigating rate control in wireless multi-hop networks. This research was motivated by TCP congestion control throughput degradation [START_REF] Gerla | TCP over Wireless Multi-hop Protocols: Simulation and Experiments[END_REF] and severe unfairness [START_REF] Xu | Revealing TCP Unfairness behavior in 802.11 based Wireless Multi-hop Networks[END_REF] in such networks. Early work on wireless rate control aimed at either improving the performance of a multi-hop TCP flow using techniques that reduce flow self-contention and packet losses (e.g., reducing TCP transmission rate or window size) [START_REF] Altman | Novel delayed ACK techniques for improving TCP performance in multihop wireless networks[END_REF]- [START_REF]Gateway Adaptive Pacing for TCP across Multihop Wireless Networks and the Internet[END_REF], or radically redesigning the transport protocol for multi-hop wireless environments as in [START_REF] Anantharaman | ATP: A Reliable Transport Protocol for Ad-hoc Networks[END_REF] and [START_REF] Sinha | WTCP: A reliable transport protocol for wireless wide-area networks[END_REF]. In addition, [START_REF] Shi | Measurement and Modeling of the Origins of Starvation in Congestion Controlled Mesh Networks[END_REF] and [START_REF] Yang | Improving fairness among TCP flows crossing wireless ad hoc and wired networks[END_REF] proposed link-layer techniques that slow down nodes along the multihop path to counter TCP unfairness.

Alternatively, [START_REF] Qiu | A general model of wireless interference[END_REF], [START_REF] Gambiroza | End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks[END_REF], [START_REF] Xu | Enhancing TCP Fairness in Ad Hoc Wireless Networks Using Neighborhood RED[END_REF]- [START_REF] Jindal | Characterizing the Achievable Rate Region of Wireless Multi-hop Networks with 802.11 Scheduling[END_REF] viewed wireless congestion as a neighborhood phenomenon rather a per flow problem. Thus, nodes in a congested neighborhood collaborate in detecting and resolving the congestion situation. Irrespective of the particular mechanism of such rate control schemes, nodes in these schemes explicitly exchange information that reflect their participation in the congestion state (e.g. queue length [START_REF] Qiu | A general model of wireless interference[END_REF], [START_REF] Xu | Enhancing TCP Fairness in Ad Hoc Wireless Networks Using Neighborhood RED[END_REF], [START_REF] Rangwala | Interferenceaware fair rate control in wireless sensor networks[END_REF], or outgoing links' capacities and offered loads [START_REF] Gambiroza | End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks[END_REF]) in order to allow different nodes to compute their appropriate transmission rates. Then, nodes communicate their calculated rates in order to insure that all flows in the neighborhood are fairly sharing the available resources.

However, none of the prior work formulates the rate control problem in multi-hop mesh networks based on the system properties identified in this paper. Unlike TCP-specific schemes [START_REF] Altman | Novel delayed ACK techniques for improving TCP performance in multihop wireless networks[END_REF]- [START_REF]Gateway Adaptive Pacing for TCP across Multihop Wireless Networks and the Internet[END_REF], GAP is a link-layer solution that is independent of the transport protocol. Moreover, our rate control approach does not deteriorate the network throughput with unnecessary control message exchanges which can cause severe throughput degradation over the wireless medium [START_REF] Camp | A Measurement Study of Multiplicative Overhead Effects in Wireless Networks[END_REF].

VIII. CONCLUSIONS

In this work, we exploit the specific properties of spatially biased 802.11 mesh networks that drive the rate control problem in such systems. We present GAP, an elastic rate control mechanism in which the set of nodes with spatial advantages, in terms of gateway access, locally and collaboratively control their transmission rates to share the gateway resources with other spatially disadvantaged nodes. We present a simple analytical model that isolates the system's properties driving our rate control scheme and use it to analyze the proposed GAP framework. Finally, we use simulations to show that GAP achieves comparable performance with overhead-prone algorithms without deteriorating the system's throughput via explicit rate control messaging.

  Single competing flow. (b) Six distributed competing flows.

Fig. 2 .

 2 Fig. 2. Examples of topologies of a two-hop node competing with single-hop node(s). Dotted lines indicate that connected nodes are within sensing range.

Fig. 3 .

 3 Fig. 3. Experimental demonstration of 802.11 approximate priority property.

Fig. 4 .

 4 Fig. 4. Fluid system model.

  Four two-hop branches.

Fig. 5 .

 5 Fig. 5. The instantaneous throughput of the two node sets S and M and the gateway utilization while varying the multi-hop set load.

  Eight two-hop branches.

Fig. 6 .

 6 Fig. 6. Throughput of the two node sets S and M, and aggregate gateway utilization under saturated demands.

( a )

 a No estimation error. (b)±40% estimation error.

Fig. 7 .

 7 Fig. 7. System behavior due to the GAP mechanism with and without estimation uncertainty.

Fig. 8 .

 8 Fig. 8. The instantaneous throughput of the two competing sets S and M, and the gateway utilization with different available information.

TABLE I CONVERGENCE

 I TIME AND ACCURACY OF DIFFERENT ALGORITHMS.

							100%	B D = 20% err x =0%	M 1 (2-hop) S 1 (1-hop)	100%	B D = 20% err x =40%	M 1 (2-hop) S 1 (1-hop)
							Throughput	40% 60% 80%	S 2 (1-hop)	Throughput	40% 60% 80%	S 2 (1-hop)
								20%	20%
								0%	0	100 200 300 400 500 600 700	0%	0	100 200 300 400 500 600 700
								Time [sec]	Time [sec]
			Single Branch	Eight Branches
	Parameter	GAP	GAP	IFA	GAP	GAP	IFA
		256K	512K		256K	512K
	t rise [s]	0.9857 1.0341 0.3040	0.0170 0.0224 0.3564
	t decay [s]	0.0645 0.0484 0.3867	0.0332 0.0024 0.4045
	E [%]	6.7035 5.7925 5.63	32.226 15.075 13.39

All authors were with Rice when the research for this work has been started. This research was supported by NSF grants CNS-0751173 and CNS-08102501 and by the Cisco Collaborative Research Initiative.


J F David

J F Ponge

F Delecour

The saprophagous macrofauna of different types of humus in beech forests of the Ardenne (Belgium)

Keywords: Soil macrofauna, beech forest, humus type, mull formation

All the macrofauna were sampled in the litter and deep soil of thirteen beechwoods, situated within the same geographical and geological area (the central Ardenne), but with different humus types: mesotrophic mull, dystrophie mull, moder and dysmoder. The analysis of data for 21 saprophagous taxa in 96 sampling units showed that the mesotrophic mull community was characterized not only by Lumbricidae (anecic, endogeic and some epigeic species), but also by many other epigeic taxa, pertaining mainly to Diplopoda, Isopoda and Gastropoda. By contrast, Elaterid larvae were one of the few taxa that were abundant in moder and dysmoder soils. The results from the Ardenne, with regard to the high density and diversity of the saprophagous macrofauna in forest mull, have confirmed other results in the literature, which gives them a large significance.

The results also emphasize the interest of experimental studies dealing with interactions between different saprophagous species, during the process of formation of forest mull.

Introduction

2

For more than a century, the very high abundance of earthworms (Oligochaeta: Lumbricidae) in mull-type humus has often been emphasized. However, the study carried out by [START_REF] Bornebusch | The fauna of forest soil[END_REF] in forests of Denmark has shown that mull soils are distinguishable from moder and mor soils not only by the abundance of Lumbricidae, but also by the high abundance of other taxa of the saprophagous macrofauna, such as Diplopoda, Isopoda and Gastropoda. The fact that different taxa may occur in the same site at high densities feeding on similar food resources, has sometimes been questioned on a speculative basis, with reference to interspecific competition (e.g. [START_REF] Kime | Spatio-temporal distribution of European millipedes[END_REF] for Diplopoda and Lumbricidae). In fact, this question has not been resolved because there have been few other comparative studies taking into account all the soil macrofauna. Literature syntheses, such as Peterson & Luxton (1982), are of limited value for testing these relationships, as they compared data obtained from different areas, in different years and with different methods. As for studies explicitly designed for the comparison of macrofaunal abundance in different humus types, their sampling programmes were not always adapted to the census either of macroarthropoda [START_REF] Eaton | The fauna of forest-humus layers in New York[END_REF], or of deep burrowing earthworms ( [START_REF] Van Der Drift | The soil animals in an oak-wood with different types of humus formation[END_REF]. A noticeable exception was the comparison between the fauna of a mull and a moder recently made by [START_REF] Schaefer | The soil fauna of beech forests: comparison between a mull and a moder soil[END_REF] in Germanythough on very different substrata (the mull on limestone and the moder on acid soil).

In the present study, sampling of the soil macrofauna was carried out simultaneously in a number of beechwoods of the central Ardenne (Belgium), with methods that made it possible to take the census of both epigeic and endogeic populations, in order to compare the structure of saprophagous communities in humus types ranging from mull to dysmoder.

Materials and methods

Features of the sites

Thirteen beechwoods were chosen within a radius of about 20 km. All of them were on a common substratum, consisting of Eodevonian schists and sandstones. Detailed botanical and pedological features of the sites are provided by [START_REF] Manil | L'humus, facteur de station dans les hêtraies acidophiles de Belgique[END_REF] and [START_REF] Thill | Typologie et potentialités forestières des hêtraies naturelles de l'Ardenne centrale[END_REF], and one can also refer to these papers for information about the climate and topography of the central Ardenne. General characteristics of the sites are given in table 1, notably the type of humus according to [START_REF] Delecour | Essai de classification pratique des humus[END_REF]. Owing to the acidity of the soil, moder and dysmoder soils were the most common, but there were also one mesotrophic and two dystrophic mull soils for comparative purposes.

Sampling of the soil macrofauna

A total of 96 sampling units (s.u.) were taken in the thirteen sites: six s.u. in each site in June and October 1989, then six more s.u. in sites Nos. 1, 4 and 6 in May and October 1990. The procedure for each s.u. was as follows:

(i) The litter and the upper soil layer were collected in a 30 x 30 cm quadrat (1/11 m 2 ), in order to extract invertebrates by means of Tullgren funnels (25 cm in diameter; 13 cm in height above the grid; fitted with 40 W bulb). (ii) The same depth of litter and soil was removed froma 50 x 50 cm quadrat (1/4 m 2 ), and 51 of 0.3% formaldehyde solution were applied to this area to expel the deep soil macrofauna. 5 l of 0.4% solution and 5 l of 0.5% solution were added at ten-minute intervals. (iii) The underlying soil was finally dug from a 30 x 30 cm quadrat and sorted by hand on a cloth.

Most invertebrates were weighed alive in the laboratory, after cleaning on a wet filter paper. Some of them were weighed after preservation in 70% ethanol or 4% formaldehyde for less than a week. The results are expressed as number of individuals per m 2 and fresh biomass (mg) per m 2 .

Taxonomy

The macrofauna taken into account in this study include the taxonomie groups listed by [START_REF] Petersen | A comparative analysis of soil fauna populations and their role in decomposition processes[END_REF], with the exception of very small subgroups such as Chironomid larvae whose individual biomass was on average less than 1 mg. Individuals were identified according to [START_REF] Brauns | Terricole Dipterenlarven[END_REF][START_REF] Vandel | Isopodes terrestres (Pemière partie)[END_REF], 1962), [START_REF] Runham | Terrestrial slugs[END_REF], [START_REF] Bouché | Lombriciens de France. Ecologie et systématique[END_REF], [START_REF] Klausnitzer | Ordnung Coleoptera (Larven)[END_REF], [START_REF] Demange | Les mille-pattes[END_REF] and [START_REF] Mcalpine | Manual of neartic Diptera[END_REF]. As far as possible, determination was carried on up to specific or generic level, but in some cases only family or subfamily was specified. That was the case for the Trichoniscinae (Isopoda) where the generic characters of the smallest individuals were not always obvious, and in most Insect larvae. No attempt was made to identify the different species of snails (Gastropoda, Stylommatophora).

Data analysis

The data for 21 taxa in 96 s.u. were ordinated in reduced space by means of multidimensional analyses. Several methods were compared: principal component analysis (PCA) and correspondence analysis (CA), processing either original data (x), or data transformed into log (x + 1). The log transformation reduces the weight of s.u. in which one species concentrates, on account of highly aggregated distribution. Computation was made using MacMul and GraphMu packages [START_REF] Thioulouse | Statistical analysis and graphical display of multivariate data on the Macintosh[END_REF]. In CA, the data displayed in the principal plane were symbolized by ellipses; their centre corresponds to usual co-ordinates and their horizontal and vertical amplitudes are proportional to the factorial variances on the studies axes.

The differences in absolute abundance between the different humus types were tested by means of Mann-Whitney U-tests (Sokal & Rohlf, 1981).

Results

Taxonomic composition

The saprophagous macrofauna sampled in the beechwoods of the Ardenne was divided into the 21 following taxa: This set of taxa found in the samples should not be regarded as a complete faunal survey in the area. Other species probably live in the soils of the beechwoods of the Ardenne, even in the studied sites. For instance, [START_REF] Gaspar | Recherches sur l'écosystème forêt: les Lombriciens des sols forestiers Ardennais[END_REF] collected two other Lumbricid species (Dendrobaena subrubicunda and Eisenia eiseni), in addition to the eight mentioned above. The list of macroarthropod species also seems too limited to be complete.

Community analysis

Using both PCA and CA, only the first axis segregated sets of sampling units which fitted in with the sites. The other axes were generated by the high frequency of particular groups in only one or two s.u. per site, and their validity must be proved by further samples. This may be a consequence of taking relatively few s.u. in each site, for some species with highly aggregated distribution patterns.

The ordination on the first axis was similar with all methods, and the result obtained with CA of log transformed data is shown in fig. 1. There was a clear-cut distinction between the s.u. of site No. 1 (mesotrophic mull), corresponding to a large variety of taxa, and the s.u. of sites Nos. 3,4,5,6,7,8,10,11,12 and 13 (either moder or dysmoder), corresponding to a lower number of taxa where Elaterid larvae predominated. The s.u. of sites Nos. 2 and 9 (dystrophic mull) were in a middle position, for they shared taxa with site No. 1, and Elaterid larvae were comparatively less numerous than in the other sites.

In site No. 1, the saprophagous macrofauna included (i) many epigeic forms (the most characteristic of which were P. conspersum, L. hypnorum, A. nitidus, I. scandinavius, Craspedosoma sp. and Stylommatophora), (ii) the endogeic forms Aporrectodea sp. and O. cyaneum, and (iii) one anecic species, as defined by [START_REF] Bouché | Lombriciens de France. Ecologie et systématique[END_REF], L.

terrestris. The low factorial variance of all these taxa on the first axis showed that they were characteristic of site No. 1. In contrast, taxa nearer to the origin on the first axis, such as Arion sp., Lumbricus sp. and Diptera larvae, had a high factorial variance on this axis, which showed that they were present in a wider range of s.u., in association with either the fauna of site No. 1 or Elaterid larvae.

Absolute abundance

The mean density during the time of the study, expressed as individual number and fresh biomass per m 2 , is given in table 2 for each of the 21 taxa in each type of humus (mesotrophic mull, dystrophic mull, moder and dysmoder). Although, according to CA, moder and dysmoder soils were not segregated by their saprophagous macrofauna, they were still treated separately. It should be noted that the mean values of density were worked out to emphasize differences between humus types, but that this was somewhat arbitrary, in so far as the figures were far from being homogeneous in all the sites with the same type of humus. However, it is clear that, in the mesotrophic mull, the saprophagous macrofauna was not only more varied, but also significantly more abundant than in the other types of humus, in individual number as well as in biomass (P < 0.001 in all the U-tests for differences between total abundance values). First, this high density was due to eight taxa characteristic of the mesotrophic mull which were completely absent elsewhere. Secondly, other taxa present in several types of humus were significantly more abundant in the mesotrophic mull, namely L. terrestris (P < 0.01), Dendrobaena sp. (P < 0.001), Trichoniscinae (P < 0.01) as regards individual number and biomass, and G. hexasticha (P < 0.05) as regards biomass.

On the other hand, total individual number and biomass were not significantly different between the other three types of humus. This means that dystrophic mull soils are more distinguishable from moder and dysmoder soils by the taxonomic composition than by the abundance of the macrofauna. From this standpoint, the statistical analysis of table 2 taxon by taxon confirmed some results obtained by CA: in particular, there were significantly fewer Elaterid larvae in dystrophic mull than in dysmoder (P < 0.01 for individual number).

Discussion

The comparison of forest sites with the same tree species, situated within the same geographical and geological area, has shown that the composition and abundance of the saprophagous macrofauna vary greatly according to the type of humus. Though two objections can be made to this first conclusion -(i) one single mesotrophic mull was studied in the Ardenne; (ii) the mull soils of sites Nos. 1, 2 and 9 corresponded to the lowest sites (cf. table 1), so that the differences in fauna could relate to altitude rather than humus type -, the results are nevertheless consistent with those in the literature, as regards the relationship between macrofauna and humus type. The general trends underscored by [START_REF] Bornebusch | The fauna of forest soil[END_REF] and confirmed by [START_REF] Schaefer | The soil fauna of beech forests: comparison between a mull and a moder soil[END_REF], have held true in respect of the beechwoods of the Ardenne. The mesotrophic mull was characterized by the high abundance of Diplopoda (in particular Iulida, Glomerida and Craspedosomatida), Isopoda and Gastropoda (in particular snails), in addition to Lumbricidae. Furthermore, the Lumbricid community was characterized just as much by endogeic species (A. caliginosa, A. rosea and O. cyaneum), as by the anecic species L. terrestris. Some epigeic Lumbricidae were also much more abundant in the mesotrophic mull (in the genus Dendrobaena but not in the genus Lumbricus, as far as the Ardenne is concerned). This confirms that the saprophagous macrofauna of forest mull constitute communities with a high species diversity, where there is a tendency for most taxa to cohabit at high density levels. On the contrary, Elaterid larvae were one of the few taxa that were particularly abundant in moder and dysmoder, another fact already reported by Bornebusch and Schaefer & Schauernann. In the Ardenne, these larvae were the only taxon of the saprophagous macrofauna met with in some dysmoder humus (e.g. site No. 13).

Two further comments must be made on the significance of these results.

1. In spite of their consistency with data from the literature, the results should not be given too general significance. In fact, the number of studies taking into account all the soil macrofauna remains low compared with the variety of natural conditions in forest ecosystems. That is why [START_REF] Kime | Spatio-temporal distribution of European millipedes[END_REF] contentionthat high density of earthworms could have a negative effect on litter-dwelling macroarthropoda -may prove correct in some instances. [START_REF] Zachariae | Spuren tierischer Tätigkeit im Boden des Buchenwaldes[END_REF] referred to some concrete cases involving high densities of anecic earthworms in beech forests of central Europe, while considering they were exceptions; in the opinion of this author, "complete macrofauna" (i.e. with a high species diversity) were more common in mull-type humus.

2. No relationship of cause and effect between macrofauna and humus type could be established by the pesent study. One cannot overlook the fact that sampling does not make it possible to know to what extent soil fauna are merely attracted to mull conditions, and to what extent they really contribute to the mull morphology. Mull and moder/dysmoder are two ecological systems which differ in many descriptors (not only saprophagous macrofauna, but also herb layer, microflora, microfauna, mesofauna and many physicochemical properties of the soil), and a distinction between determining and secondary descriptors can only be made on experimental bases. However, a thorough knowledge of the dwellers of different humus types is of great interest to tackle experimental studies. For example, the biomass figures suggest that the formation of mull in temperate forests may not involve anecic species alone, nor Lumbricidae alone. In the present study, it was on average 12,762 mg/m 2 for L. terrestris vs. 12,732 mg/m 2 for the other taxa, epigeic and endogeic taken as a whole (cf. table 2).

And though it is true that all the endogeic forms are Lumbricidae, on the other hand, epigeic forms which play an important role in the breakdown of leaf litter belong to a great extent to other groups, mainly macroarthropoda; that was the case for the majority of individuals, and 40% of biomass, in the epigeic forms of the mesotrophic mull of the Ardenne. Consequently, experimental studies which aim at understanding the role of the saprophagous macrofauna in mull formation should take into account the high species diversity of communities, and focus not only on the action of big anecic earthworms, but also on possible interactions between epigeic and endogeic species [START_REF] David | Relations entre les peuplements de Diplopodes et les types d'humus en forêt d'Orléans[END_REF][START_REF] Scheu | Die Rolle endogäischer Regenwürmer im Ökosystem Kalkbuchenwald und ihr Zusammenwirken mit saprophagen Makroarthropoden[END_REF].

  (i) Five in the Lumbricidae (Oligochaeta): the species Lumbricus terrestris and Octolasium cyaneum; the genera Aporrectodea sp. (including at least A. caliginosa and A. rosea), Dendrobaena sp. (including at least D. octaedra and D. rubida) and Lumbricus sp. (including at least two other species, L. castaneus and L. rubellus). (ii) Six in the Diplopoda: the species Allajulus nitidus, Glomeris hexasticha and Iulus scandinavius; the genera Chordeuma sp. (including at least C. sylvestre), Craspedosoma sp. and Polydesmus sp. (undetermined species for lack of adult males). (iii) Three in the Isopoda: the species Ligidium hypnorum and Porcellium conspersum; the subfamily Trichoniscinae (including at least Trichoniscus pusillus). (One individual of Oniscus asellus, collected in site No. 8, was not taken into account in the analyses). (iv) Two in the Gastropoda: the genus Arion sp.; the order Stylommatophora (including several other species of snails). (v) Five in Insect larvae: the species Enoicyla pusilla (Trichoptera); the genus Fannia sp. (Diptera); the subfamily Tipulinae (Diptera); the families Elateridae (Cole optera) and Sciaridae (Diptera).

Fig. 1 .

 1 Fig. 1. Above: Display of 21 taxa in the principal plane of the CA (A.n.: A. nitidus; Ap.: Aporrectodea sp.; I.s.: I. scandinavius; P.c.: P. conspersum; St.: Stylommatophora). Below: Ordination of the sampling units from each site on the first axis of the same CA

Fig. 1

 1 Fig. 1

Table 1 .

 1 Situation and main features of the 13 studied beechwoods

	Site N°	Nearest village	Lambert coordinates	Altitude	Vegetation	Humus type
			(Longit./Latit.)	(m)
	1	Saint-Hubert	221, 92/85, 26	350	Melico-Fagetum festucetosum	mesotrophic mull
	2	Saint-Hubert	221, 93/85, 20	370	Luzulo-Fagetum festucetosum	dystrophic mull
	3	Saint-Hubert	220, 81/85, 69	380	Luzulo-Fagetum vaccinietosum	dysmoder
	4	Saint-Hubert	222, 00/84, 82	465	Luzulo-Fagetum festucetosum	moder
	5	Saint-Hubert	222, 03/84, 52	500	Luzulo-Fagetum typicum	moder
	6	Saint-Hubert	222, 90/83, 96	505	Luzulo-Fagetum vaccinietosum	dysmoder
	7	Haut-Fays	197, 13/80, 02	390	Luzulo-Fagetum festucetosum	moder
	8	Haut-Fays	195, 86/79, 93	400	Luzulo-Fagetum typicum	moder
	9	Houdremont	186, 81/69, 19	375	Luzulo-Fagetum festucetosum	dystrophic mull
	10	Willerzie	183, 38/73, 48	385	Luzulo-Fagetum vaccinietosum	dysmoder
	11	Willerzie	185, 97/72, 40	430	Luzulo-Fagetum typicum	moder
	12	Willerzie	183, 67/72, 99	430	Luzulo-Fagetum vaccinietosum	dysmoder
	13	Willerzie	185, 94/72, 27	445	Luzulo-Fagetum vaccinietosum	dysmoder

Table 2 .

 2 Mean density, expressed as individual number and fresh biomass, for 21 saprophagous taxa in 4 types

	humus
	mesotrophic mull	dystrophic mull	moder		dysmoder
	(site No. 1)		(sites Nos. 2, 9)	(sites Nos. 4, 5, 7, 8, 11)	(sites Nos. 3, 6, 10, 12, 13)
	(12 s. u.)		(12 s. u.)		(36 s. u.)		(36 s. u.)
	Ind./m 2	mg/m 2	Ind./m 2	mg/m 2	Ind./m 2	mg/m 2	Ind./m 2	mg/m 2

Acknowledgements

We are very grateful to R. D. Kime for his helpful comments, and we are indebted to F. Baarslag for his technical cooperation.