Thomas Begin

Bruno Baynat

Isabelle Guérin-Lassous

Thiago Abreu

Performance analysis of multi-hop flows in IEEE 802.11 networks: A flexible and accurate modeling framework

Keywords: Multi-hop wireless network, Multi-hop path, IEEE 802.11, Modeling Framework, Performance Evaluation

Multi-hop wireless networks are often regarded as a promising means to extend the limited coverage area offered by WLANs. However, they are usually associated with poor and uncertain performance in terms of available bandwidth and packet losses, which clearly stands as a limitation to their use. In this paper, we consider the performance evaluation of a multi-hop path (also called chain), based on the IEEE 802.11 DCF. The proposed modeling framework is constructive and versatile, so that it can handle various types of multi-hop wireless paths, including scenarios with two flows in opposite directions, and topologies where nodes are exposed to the well-known hidden node problem. The models derived from our framework are conceptually simple, easy to implement and produce generally accurate results for the attained goodput of flows, as well as the datagram loss probability. Typical relative errors for these two quantities are below a few percent. Also, fundamental phenomena occurring in multi-hop wireless networks, such as performance collapse and starvation, are well captured by the models.

I. INTRODUCTION

Wireless networks are increasingly becoming a standard way for end users to access onlineservices hosted on the Internet. The volume of traffic passing through these networks is rapidly growing, fuelled by the introduction of new applications and connected devices which, in turn, drives the ever-increasing demand for bandwidth. Currently, most wireless local area networks (WLANs) are based on the IEEE 802.11 distributed coordination function (DCF) standard, which implements a probabilistic medium access control (MAC) layer. WLANs are overwhelmingly deployed in the infrastructure mode, where all nodes, typically close to each other, communicate through an access point, which acts as a bridge between the wireless and wired networks.

Unlike WLANs operating on the infrastructure mode, multi-hop wireless networks include wireless relay nodes, and are often regarded as a promising means for extending the limited coverage area associated with WLANs. Flows may then have for a source a node that is several wireless hops away from their ultimate destination. For instance, Figure 1 depicts an example of a multi-hop wireless network with 12 nodes and 3 multi-hop flows. Multi-hop wireless networks are usually associated with poor performance (e.g., available bandwidth is scarce and packet losses due to collisions are numerous). More importantly, not only do the actual performance of a multi-hop network tend to be low but they are, in general, hardly predictable. This uncertainty in the assessment of the overall behavior of multi-hop networks is due to many factors such as the complex interactions between neighboring nodes, the non-uniform spread of the workload among the nodes, the occurrence of nodes handling several flows having possibly different destinations and the prevalence of frame collisions due to the hidden node problem. Note that difficulties existing for the case of single-hop paths (e.g., radio channel quality, antenna power, buffer size) also apply in the multi-hop case. This lack of forecast in the expected performance of multi-hop networks is a clear limitation to their use. A smart and virtually costless way to improve the performance of a multi-hop wireless network can simply consist of tuning some of its parameters in a better way. Examples of possible beneficial actions are many and include: resizing the size of the buffers at nodes, changing the transmitting power of nodes and shifting the node positions (assuming they are mobile).

wmn.pdf

However, making the right choice can be made much easier with the help of accurate performance evaluation and sizing tools.

There is a large body of literature devoted to the analytical performance evaluation of wireless networks. Accurate and sound models have been proposed for the case of a single cell (i.e., no multi-hop) [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]. Relaxing the assumption that all nodes can sense each other's transmissions, relevant analytical models exist when flows are transmitted over a single-hop path. These models provide a better understanding of some of the fundamental principles ruling these wireless networks [START_REF] Garetto | Modeling media access in embedded two-flow topologies of multi-hop wireless networks[END_REF]. However, in the more general case, where flows may traverse paths with multiple hops, and several flows may compete to get access to nodes transmission resources, little progress has been made. This shortage may be due to the apparent complexity of these networks, where many factors need to be taken into account (e.g., the hidden and exposed node problems and the fact that periods where backoff periods are frozen are erratic), which precludes the design of adequate theoretical models.

In this paper, we focus our efforts on the performance evaluation of a single multi-hop path (also called chain) that is traversed by one or two flow(s). Though this clearly does not address the full scope of multi-hop wireless networks, we believe it can represent a significant milestone in this direction. More specifically, the contributions of this paper are threefold. First, we provide a constructive and versatile mathematical framework to derive easy-to-handle analytical models of multi-hop paths based on the IEEE 802.11 DCF. Its originality comes from its two-level abstraction: the high-level mostly seeks to mimic the buffer behavior of nodes along the path, while the low-level estimates the delay for transmitting a packet according to the IEEE 802.11 DCF, given the surrounding environment of a node. Second, we instantiate this framework on several case studies, including configurations where two flows in opposite directions travel along the path, and topologies where nodes are exposed to the well-known hidden node problem. Third, we assess the accuracy of the derived models using a discrete event simulator, and we show that these latter capture some of the fundamental phenomena occurring in multi-hop wireless networks such as performance collapse and starvation.

II. RELATED WORK

There is a large body of literature devoted to the performance modeling of the IEEE 802.11 protocol. The proposed models handle a large variety of problems. The differences include the specific topology of interest (cells or multi-hop networks), the assumptions on the generated traffic (while some studies restrict their analysis to the sole case of saturated traffic sources at nodes, others cover the more general case of nodes in the non-saturated regime), the length of paths on which flows are routed (single-hop path versus multi-hop path), the properties of the physical layer (e.g., perfect or non-perfect with bit error rate (BER)), the length (if any) of the buffer at nodes (to buffer datagrams before transmission), as well as some specific DCF mechanisms (e.g., retransmission limit).

In the case of a cell (i.e., a single-hop network in which each node senses the transmission of each other), Bianchi [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF] developed a seminal model based on a Discrete-Time Markov Chain to evaluate the attainable throughput of the cell. In this work, the author assumes that every node runs in a saturated regime, and that frame transmissions are not exposed to either a BER, or a retransmission limit. Several follow-up studies were carried out to better match some IEEE 802.11 mechanisms [START_REF] Tinnirello | Refinements on IEEE 802.11 distributed coordination function modeling approaches[END_REF] (and the references therein), to include a more realistic radio channel with the presence of a BER [START_REF] Vishnevsky | 802.11 lans: Saturation throughput in the presence of noise[END_REF], or to cover non-saturated scenarios [START_REF] Malone | Modeling the 802.11 distributed coordination function in nonsaturated heterogeneous conditions[END_REF]. However, all these latter studies are devoted to a single cell scenario, thereby bypassing the hidden node problem (since each node senses all other transmissions) as well as the strong correlations between nodes in a chain.

For multi-hop wireless networks, where nodes are not necessarily in each other's carrier sensing range, existing works typically fall into two categories depending on the length of the paths on which flows are routed, i.e., single-hop versus multi-hop. In the case of a single-hop path, in which the source and the destination are only one hop away, Wang and Kar [START_REF] Wang | Throughput modelling and fairness issues in CSMA/CA based ad-hoc networks[END_REF] developed a Markovian model to evaluate the average throughput of flows. To simplify their analysis, the authors assume no binary exponential backoff, a perfect physical layer (no BER) and a Request to Send / Clear to Send (RTS/CTS) mechanism that never experiences failures. Moreover, they assume all nodes to be identical in terms of workload. In [START_REF] Qiu | A general model of wireless interference[END_REF], Qiu et al. proposed an hybrid approach to predict the achievable throughput between sources and destinations that are one hop away. They designed an analytical model, whose parameterization is based on a empirical pre-processing step that measures the actual radio condition of each node. In another set of works, the authors of [START_REF] Garetto | Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks[END_REF], [START_REF] Garetto | Modeling media access in embedded two-flow topologies of multi-hop wireless networks[END_REF], [START_REF] Nardelli | Closed-form throughput expressions for CSMA networks with collisions and hidden terminals[END_REF] proposed analytical models to derive the throughput of flows transmitted on single-hop paths. Nardelli and Knightly come up with a closed-form expression for the achievable throughput in [START_REF] Nardelli | Closed-form throughput expressions for CSMA networks with collisions and hidden terminals[END_REF] under the assumption that all nodes are in saturation. Their approach does not seem to allow the computation of other performance parameters of interests, e.g., the datagram loss probability. In a prior work [START_REF] Garetto | Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks[END_REF], that generalizes the approach proposed in [START_REF] Garetto | Modeling media access in embedded two-flow topologies of multi-hop wireless networks[END_REF], the authors use an iterative approach to estimate parameters like flow throughput and frame loss probability. However, the non-saturated case study is based on the assumption that the sending throughput of a node equals the receiving throughput of the same node. This is clearly not the case when the links do not have the same quality. Tsertou and Laurenson demonstrated that the latter approach can be significantly inaccurate, especially when dealing with small contention window sizes and large data packet transmission times [START_REF] Tsertou | Revisiting the hidden terminal problem in a csma/ca wireless network[END_REF]. In the same paper, the authors proposed a new method to estimate the frame collision probability along with the attained throughput. Their approach is mostly thought to cope with the classical (symmetric) hidden node problem. In the case of a multi-hop flow, which is our case of interest, the hidden node problem that is encountered arises as being asymmetrical since the nodes producing collisions are not equally exposed to collisions.

When it comes to the case of multi-hop flows, i.e., flows whose source and destination can not directly communicate, there is only a handful of works that have tackled analytically the performance analysis of flows conveyed through a path. In [START_REF] Aziz | Models of 802.11 multi-hop networks: Theoretical insights and experimental validation[END_REF], Aziz et al. highlighted some of the complex phenomena emerging in a wireless path (e.g., mutual exclusion of links and unfairness between the nodes). In particular, they studied the evolution of the queue length at the buffer nodes, and they emphasized their correlation (some queues may be empty, while others are not). In the same work, the authors also proposed an analytical model, which applies only when every node of the path, including the relay nodes, is in a saturated regime (i.e., it always has a datagram waiting to be transmitted), which appears as a strongly simplifying assumption.

In a separate work [START_REF] Hira | Throughput analysis of a path in an IEEE 802.11 multihop wireless network[END_REF], Hira et al. proposed to estimate the maximum attainable throughput of the path by assuming that its value approximately corresponds to the actual capacity of the bottleneck link (i.e., the link that takes the longest time to transmit a datagram). By successively iterating on the nodes of the path, they estimate the delay incurred by the transmissions of neighbor nodes on the transmission time of a datagram in order to update its current value. Such an approach does not seem to allow the computation of the datragam loss probability. A similar approach was developed by Ng and Liew in [START_REF] Ng | Throughput analysis of IEEE 802.11 multi-hop ad hoc networks[END_REF]. Although the authors considered the impact of hidden nodes in their framework, they assume a perfect physical layer, saturated sources, and buffers with infinite sizes. Jindal and Psounis, of [START_REF] Jindal | The achievable rate region of 802.11-scheduled multihop networks[END_REF] proposed an original approach that aims to partition a multi-hop network into several two-edge topologies (i.e., two distinct edges not sharing the same transmitter) in order to characterize the achievable rate of each edge of the network.

Unlike our modeling framework, they assume a large buffer size in order to overlook the potential datagram losses. Very recently, Aydogdu and Karasan designed an analytical model to estimate the goodput of nodes in an arbitrary multi-hop network [START_REF] Aydogdu | Goodput and throughput comparison of single-hop and multi-hop routing for[END_REF]. To better match the reality, each node is equipped with a finite buffer. Unlike our paper, the authors assume a perfect physical layer and the systematic use of the RTS/CTS mechanism. The proposed model relies on a semi-Markov chain, introduced formerly in [START_REF] Aydogdu | An analysis of IEEE 802.11 DCF and its application to energy-efficient relaying in multi-hop wireless networks[END_REF], and that is solved by an iterative procedure. The authors then derive a set of probabilities, such as, for example, the frame collision probability. Although the proposed models are generally accurate, in some cases (e.g., small irregular topologies and moderate workload), their accuracy may significantly decrease. As pointed out by the authors, this may be due to the assumption of a common collision probability for each node. In our case, considering more specific scenarios, we can derive frame collision probabilities that may differ on each link of the path.

To summarize, there is only a few works devoted to the analytical performance evaluation of IEEE 802.11 in the case of multi-hop networks with multi-hop flows. Besides, it seems that none of them handles at the same time realistic assumptions regarding the behavior of the MAC protocol, the inter-dependencies in the distribution of the workload among the nodes (some nodes may be in saturation while others may be in starvation), the hidden node problem, and the finite size of buffers. In a previous work [START_REF] Abreu | Hierarchical Modeling of IEEE 802.11 Multi-hop Wireless Networks[END_REF], we presented an analytical model for the performance analysis of a multi-hop flow in a three-node path. Because our model features buffers of finite size at each node, it captures the potential starvation state (i.e., empty buffers) of relay nodes, even if the first node of the path may be in saturation. However, this latter model was restricted to the case of a three-nodes scenario, in which the hidden node problem does not exist, thereby preventing virtually all frame collisions. In a follow-up work [START_REF] Abreu | Modeling of IEEE 802.11 multi-hop wireless chains with hidden nodes[END_REF], we extended this model to a four-nodes scenario, in which collisions due to hidden nodes may arise. Compared to our former studies [START_REF] Abreu | Hierarchical Modeling of IEEE 802.11 Multi-hop Wireless Networks[END_REF], [START_REF] Abreu | Modeling of IEEE 802.11 multi-hop wireless chains with hidden nodes[END_REF], this paper provides a significant step towards demonstrating the accuracy and the versatility of our modeling framework as it includes numerous additional numerical results (thousands of examples) for the output throughput and for the datagram loss probability, as well as a complete new scenario with 2 opposite flows.

III. SYSTEM DESCRIPTION

A. IEEE 802.11 DCF

The IEEE 802.11 protocol specifies medium access control (MAC) and physical layer (PHY) for nodes within a WLAN. In its Distributed Coordination Function (DCF) mode, it fetches the datagram that is next in the waiting line for transmission (if any), and resorts to a random access scheme, inspired by the carrier sense multiple access with collision avoidance (CSMA/CA), to access the medium. Note that, at this stage, the data link layer appends additional header and trailer to the datagram, which in turn becomes a frame. A node with a frame waiting for transmission senses the channel activity. Once the channel is detected as idle for a period of time equal to a distributed interframe space (DIFS) denoted by t DIFS , the node draws a random backoff interval, which determines for how long its transmission will be postponed. This latter mechanism aims at reducing the probability of collision with frames sent by other nodes.

The backoff interval is discretized, and its value is expressed in term of slot times. Note that the length of a slot time, denoted by t SlotTime , depends on the physical layer being used (e.g., t SlotTime = 20 µs for the IEEE 802.11b). The backoff timer is (i) decremented by one for each idle slot time, (ii) frozen when the node senses a transmission on the channel, and (iii) resumed if the channel is detected again as idle for a duration of time equal to a DIFS. When the backoff timer hits 0, the node starts transmitting its frame.

The transmission of a frame and its successful reception by the destination node triggers the transmission of a positive acknowledgment (ACK), that lasts for a time t ACK , after a short interframe space (SIFS) labelled by t SIFS (dimensioned such that t SIFS < t DIFS , in order to prevent other nodes from starting their frame transmission in the meantime). If the sending node does not receive an ACK after a given time t ACKTimeout , it deems the frame as lost.

The retransmissions of lost frames are managed according to binary exponential backoff rules.

Note that the IEEE 802.11 DCF protocol sets a limit to the number of attempted transmissions.

We denote by m this maximum number of transmission attempts. All frame transmissions are postponed by a random backoff time, uniformly drawn in the interval [0, w]. Here, w refers to the size of the contention window. The actual value of w depends on the number of former failed transmissions for this frame. For the first try, w = W 1 = W min , where W min designates the minimum size of the contention window. If subsequent transmissions are needed, then the contention window is gradually expanded. More precisely, for the i-th transmission of a frame (i = 2, ..., m), the value of w is set at follows: If a node operates in RTS/CTS mode, it sends a Request-to-Send (RTS) frame, and waits, in return, a Clear-to-Send (CTS) frame (sent by the destination node) before transmitting its data frame. While the use of the RTS/CTS mechanism is a clear asset when hidden nodes communicate with an access point, its efficiency is unclear in the case of a multi-hop wireless network. Depending on the specific scenario, the RTS/CTS mechanism has been shown to be a positive (e.g. [START_REF] Ray | On false blocking in RTS/CTS-based multi-hop wireless networks[END_REF]), or negative factor (e.g. [START_REF] Xu | Effectiveness of RTS/CTS handshake in IEEE 802.11 based ad hoc networks[END_REF]) on the performance of flows. In this paper, we focus our work on a single multi-hop path that are traversed by one or two flow(s). In configurations with three nodes, there is no hidden node and the RTS/CTS mechanism is useless as it only introduces additional delays. In scenarios that involve more than three nodes, hidden nodes may occur and the use of the RTS/CTS mechanism might be useful in bringing down the rate of frame collisions. To assess the actual efficiency of the RTS/CTS mechanism, we conduct many discrete-event simulations, in which we compare the throughput attained by flows with and without the RTS/CTS mechanism. The corresponding results, reported in Figure 12 in Appendix, show that the RTS/CTS mechanism happens to be a significant negative factor in our case. The reader can refer to [START_REF] Garetto | Modeling media access in embedded two-flow topologies of multi-hop wireless networks[END_REF] to get a thorough understanding of the reasons causing this phenomenon. Because of these inefficiencies, we do not include the RTS/CTS mechanism in the general modeling framework presented in this paper. As for the EIFS, the standard defines an extended interframe space (EIFS) in lieu of DIFS when frame are erroneously received. Yet, studies show that several IEEE 802.11 cards do not implement this feature (e.g., [START_REF] Chaudet | Experiments of some Performance Issues with IEEE 802.11b in Ad Hoc Networks[END_REF], [START_REF] Bianchi | Experimental assessment of the backoff behavior of commercial IEEE 802.11b network cards[END_REF]).

w = W i = min(2 i-1 ×(W min +1)-1, W max ),
Therefore, even if our proposed framework could accommodate to the EIFS option, we present it in the next section without this feature.

In multi-hop wireless networks, two nodes can be: a) within each other's transmission range; b) out of transmission range, but inside the carrier sensing range of each other; or c) out of both transmission and carrier sensing ranges of each other's. The size of these ranges mostly depends on physical factors such as the strength of the radio signal, the channel quality and the used antennas. Clearly, the position of nodes with respect to each other has strong implications on their backoff timer decrement. Indeed, the backoff timer of a given node will be frozen each time another node within its carrier sensing range is transmitting.

B. Multi-hop path

As discussed in the introduction, this paper is devoted to the performance evaluation of a multi-hop path. We consider a multi-hop path as a sequence of N nodes such that any nodes n and n + 1 (n = 1, ..., N -1) are within each other's transmission range; any nodes n and n + 2

(n = 1, ..., N -2)
are not in the transmission range, but are in the carrier sensing range of each other; and any nodes n and m (n, m = 1, ..., N ), with |n -m| > 2, are out of both the transmission and carrier sensing ranges of each other. We refer to nodes n + 1 and n -1 as the right-hand and left-hand neighbor nodes of node n, and define d n,n+1 as the distance between node n and node n + 1. In a multi-hop path, a node n can thus only directly communicate with its right-hand neighbor and with its left-hand neighbor, but can also sense the transmissions of its 2-hop neighbors (without being able to decode their transmissions).

Each node n is equipped with a single IEEE 802.11 communication interface, and its buffer size is given by K n , which corresponds to the maximum number of datagrams being queued for transmission. A multi-hop path carries datagrams from node 1 to node N , and vice-versa.

Note that, with this definition, no datagram enters or quits the path somewhere else than at the border nodes, unless it gets lost. For the sake of simplicity, we collect all datagrams entering at node 1 (resp. node N ) into one flow, referred subsequently to as the left-to-right flow (resp. the right-to-left flow), and we let Λ r (resp. Λ l ) be its rate of datagrams arrivals. The superscript r (resp. l) stands for towards right (resp. towards left), and it allows us to discriminate precisely each flow. It follows that the workload of the multi-hop path consists of two flows in opposite directions, originating at each border node. Figure 2 illustrates the multi-hop path we consider in this paper.

The transmission speed of links depends on the radio channel quality. The mechanism used to setting it is referred to as the Auto Rate Fallback (ARF) algorithm. For the sake of easiness, we consider that the transmission speed of a link is a decreasing function of the distance of a chain2.pdf T n,n+1 as the time for node n to transmit a frame to its right-hand (resp. left-hand) neighbor, once the backoff timer has expired. Thus, it follows:

T n,n+1 = 8s c n,n+1 + t SIFS + t ACK (resp. T n,n-1 = 8s c n-1,n + t SIFS + t ACK )
. Wireless communication channels are prone to bit errors due to multipath propagation, fading and scattering. Typically, the greater the distance between two nodes, the lower the probability that a frame arrives with no bit errors. Beside this ground rule, bit errors tend to occur in bursts because the wireless channel conditions may vary slowly compared to the symbol rate.

Several models have been proposed to represent more accurately the Bit Error Rate (BER), which expresses the probability that a bit is misinterpreted at a receiver node due to the propagation process (e.g., [START_REF] Gilbert | Capacity of a burst-noise channel[END_REF], [START_REF] Turin | Modeling error sources in digital channels[END_REF], [START_REF] Willig | A new class of packet-and bit-level models for wireless channels[END_REF]). Although our proposed modeling framework can operate with such BER models, we assume, for the sake of simplicity, that the BER takes a constant value for each transmitted bit. Since the distance between the successive nodes of a multi-hop path is not necessarily constant, we let BER r n (resp. BER l n ) be the value of the BER when node n transmits to its right-hand neighbor node n + 1 (resp. left-hand neighbor node n -1). The data we used for the BER computation are reported in Section V. Based on the value of the BER r n , and on the mean size of the frames (in bytes), we can then derive the frame error rate FER r n , which stands for the probability that a frame transmitted by node n to its right-hand neighbor node n + 1, is received with error (due to the BER). This frame error rate reads as:

FER r n = 1 -(1 -BER r n ) 8s . (1)
Clearly, the same approach applies also for the computation of FER l n . In addition to errors due to the BER, a transmitted frame can also be received with errors due to collisions. A collision occurs when nearby nodes are active on the channel simultaneously.

The well-known hidden node problem causes collisions, and, in general, it occurs for multi-hop paths, unless all nodes from 1 to N are within the same carrier sensing range. Unlike the frame error rate FER, the odds of collisions highly depend on the workload level. Typically, if every node of the path has only very few datagrams to transmit, then the probability of collisions for the corresponding frames is expected to be low. We denote by COL r n (resp. COL l n ) the probability that a frame sent by node n to its right-hand neighbor (resp. its left-hand neighbor), collides with another frame, and thus gets lost. Note that there is, in general, no simple closed-form expression to assess the value of COL r n because of its complexity. In order to ease the subsequent computations, we introduce a single parameter denoted by f r n (resp. f l n ), and referred to as the frame loss probability, which stands for the probability that a frame transmitted by node n to its right-hand neighbor (resp. its left-hand neighbor), is received with error, regardless of the cause. As detailed below, a frame can be lost because of the BER or because of collisions. The frame loss probability f r n can thus be calculated as the probability that a frame is lost because of the BER, i.e., FER r n , plus the probability that the frame is lost because of a collision, i.e., COL r n , minus the probability of both events occurring simultaneously. If we further make the assumption that BER and collisions are independent events, we can estimate the frame loss probability as:

f r n = FER r n + COL r n -FER r n × COL r n . (2)
Table I summarizes the notations used in this section.

C. Behavior and performance

In a multi-hop path, a given node n can transmit to either its right-hand neighbor or its lefthand neighbor. But node n can sense the transmission of a larger set of nodes. All nodes that belong to this last set have transmissions that are mutually exclusive with those of node n (unless they start exactly at the same time) and that, in addition, can freeze the backoff decrement of node n. This implies a very strong synchronization between nodes, that must be taken into account in the model. In addition to this phenomenon, nodes that do not belong to this set can transmit frames that can collide with frames transmitted by node n. This is the well-known hidden problem, that also introduces a strong dependency between the individual behaviors of each node (through the effects of collisions).

Another factor that has a strong implication on the development of realistic models, is that the workload is often non-uniformly distributed among the nodes of the path. Indeed, because links between nodes are exposed to different conditions (e.g., BER and collisions), the time necessary to successfully send a datagram can considerably vary from one node to another (and also from one direction to the other). As a result, the level of workload at each node, corresponding to the number of datagrams waiting for transmission, can be very disparate among the nodes of the path. Some nodes may have their buffer full of queued datagrams, while in the same time, others (prior or subsequent in the path) may be in starvation (i.e., with empty buffers).

Losses should also be carefully considered when dealing with modeling. First it is important to clearly make the difference between frame losses and datagram losses. As detailed in the previous subsection, a frame can be lost either because of the BER or because of collisions. A lost frame will be retransmitted (with an increased contention window size), unless the maximum number of allowed retransmissions is reached. The collision probability is much more difficult to estimate than the frame error probability (due to BER), and represents a crucial step in the modeling process. Let us now consider datagram losses. A datagram can be lost because of two different factors: 1) if the corresponding frame is transmitted to a receiver when its buffer is full, or 2) if all successive retransmissions of the frames corresponding to the same datagram are lost.

As discussed above, the first case is very likely to happen, because of the high non-uniformity of the load in the path. On the opposite, the second case is unlikely to happen, as the probability of having m consecutive frame losses is typically very low (remember that m is the maximum number of transmission attempts allowed by the protocol for a single frame) 1 .

We conclude this section by precisely defining all the key performance parameters we want to obtain for our multi-hop path. For the sake of succinctness, we only give the definition of the performance parameters pertaining to the flow travelling from node 1 to node N (i.e., the left-to-right flow). We denote by G r the goodput of this flow, corresponding to the mean number of datagrams that reach destination node N per unit of time, and denote by L r the probability that a datagram gets lost in its path from node 1 to node N (which, as discussed earlier, is mainly due to buffer overflow). Obviously, these parameters vary with the rates of the workload Λ r and Λ l , with the position of nodes d n,n+1 , as well as with virtually all the other parameters.

In the next section, we show how we can evaluate all of these performance parameters (for both flows), namely, G r , G l , L r and L l , based solely on the parameters of the used version of IEEE 802.11, namely t SIFS , t DIFS , t ACK , t ACKTimeout , t SlotTime , W min , W max and m, as well as those coming from the multi-hop path, namely K n , d n,n+1 , c n,n+1 , s, Λ r , and Λ l .

1 Assuming that at each transmission attempt, a frame gets lost with constant and independent probability q, then the probability of loosing a datagram is: q m . For m = 7 and q = 0.6, it only amounts to a couple of percentage points.

IV. MODELING FRAMEWORK

We have developed a general modeling framework for the performance evaluation of a multihop path in a wireless network. Our model is made up of two levels: 1) a unique high-level Note that exponential service times and Poisson arrivals are strong assumptions that are made for the sake of computational simplicity. Relaxing the exponential assumption of service times would lead to a high-level model made of M/G/1/K queues that could in turn be solved easily [START_REF] Brandwajn | A conditional probability approach to M/G/1-like queues[END_REF]. Similarly, relaxing the Poisson assumption of arrivals would lead to a high-level model made of G/M/1/K queues that could also be alternately solved [START_REF] Brandwajn | A recurrent solution of Ph/M/c/N-like and Ph/M/c-like queues[END_REF]. However, both extensions would require deriving the nature of the distribution of either the service times or the interarrival times, and even if this were possible, it would drastically complicate the overall model.

queueing
Unless necessary, this is not desirable, and we will just validate numerically the accuracy of these memoryless assumptions.

Assuming that λ n and µ n are known for all n = 1, ..., N , then all performance parameters of our high-level queueing model can be obtained from the well-known results of the M/M/1/K queue. The output throughput of queue n, i.e., X n , can be derived from the probability π n (i) of having i customers in the n-th M/M/1/K queue, as:

X n = µ n (1 -π n (0)) (3)
As noted in Section III-C, the probability of loosing a datagram because the maximum number of unsuccessful retransmissions of the corresponding frame has been reached, is very low. We will thus neglect this possibility and assume that a datagram can only be lost because, upon its arrival on the next node, it finds the buffer full. As a result, X n can be considered as the average number of datagrams that are correctly transmitted per unit of time from node n either to node

n + 1 (if n ≤ N -1) or to node n -1 (if n ≥ 2).
The utilization of queue n, i.e., U n , corresponding to the proportion of time node n is not empty, is:

U n = 1 -π n (0). (4)
And finally, from the PASTA theorem [START_REF] Wolff | Poisson arrivals see time averages[END_REF], we can obtain the buffer overflow probability, i.e., P n , corresponding to the probability that a datagram is lost because the buffer of node n is found full upon its arrival instant:

P n = π n (K n ). (5)
In order to estimate the missing parameters λ n and µ n , let us first consider a given node n with n = 2, ..., N -1. Let us define q r n (resp. q l n ) the proportion of datagrams sent by node n that move to node n + 1 (resp. node n -1). We can thus split the output throughput of queue n into two opposite flows, one to the right and one to the left, as illustrated in Figure 3:

X n = X r n + X l n (6)
where X r n = X n q r n and X l n = X n q l n .

Obviously, we have: q r n + q l n = 1. Noting that the flow of customers (viz. datagrams) arriving at the entrance of queue n is the superimposition of the left-to-right flow leaving queue n -1, and of the right-to-left flow leaving queue n + 1, we derive the value of the workload λ n as:

λ n = X r n-1 + X l n+1 (8)
as well as the proportion of customers moving to the right and those moving to the left:

q r n = X r n-1 X r n-1 + X l n+1 and q l n = X l n+1 X r n-1 + X l n+1 . (9)
These last relations are true because the PASTA property ensures that the proportion of lost datagrams is the same for the right-to-left flow and for the left-to-right flow (the Poisson assumption ensures that, despite having different rates, both flows undergo equal probability to find the buffer of queue n full).

When it comes to the special case of node 1 (resp. node N ), as it is the first (resp. last) node of the left-to-right (resp. right-to-left) flow and the last (resp. first) node of the right-to-left (resp.

left-to-right) flow of the wireless network, node 1 (resp. node N ) only has to transmit datagrams to node 2 (resp. node N -1). As a result, its queue is only fed by the external workload process with rate Λ r (resp. Λ l ). This is illustrated by Figure 3. It follows that for node 1, we have:

X 1 = X r 1 , q r 1 = 1, q l 1 = 0 and λ 1 = Λ r .
Similarly, for node N , we have:

X N = X l N , q l N = 1, q r N = 0 and λ N = Λ l .
At this stage we turn to the single set of parameters that is left to determine within the highlevel queueing model, i.e., the service rates µ n . We start by considering a value of n such that n = 2, ..., N -1. We use S n to denote the mean time node n needs to transmit a datagram.

S n is just the inverse of the service rate µ n , and can be expressed as a weighted sum of two components, each of which accounting for one of the two possible next hops for the transmitted datagrams:

S n = 1 µ n = q r n S r n + q l n S l n (10)
where S r n (resp. S l n ) is the mean service time to handle a datagram headed to its right-hand (resp. left-hand) neighbor. As stated before, S r n and S l n are parameters that depend on many factors and it will be the objective of the low-level Markov chain models to provide an estimation of these parameters. Note that for the border nodes, i.e., n = 1 or n = N , the computation of S n can still be made using relation [START_REF] Nardelli | Closed-form throughput expressions for CSMA networks with collisions and hidden terminals[END_REF], even though one component in the right-hand side is zero.

If we assume that these missing mean service times are correctly estimated, then all the input parameters of the high-level model are now known. We can then solve it and derive from its performance parameters (relations (3)-( 7)), all the key performance parameters of our multi-hop path network defined in Section III-C. First, the goodput of the left-to-right (resp. right-to-left) flow corresponds to the output throughput of queue N -1 (resp. queue 2) toward the right (resp. toward the left):

G r = X r N -1 (resp. G l = X l 2 ). (11)
Then, the datagram loss probability along the left-to-right (resp. right-to-left) flow, is the probability that a datagram is lost by buffer overflow in any of the first (resp. last) N -1 queues:

L r = 1 - N -1 n=1 (1 -P n ) (resp. L l = 1 - N n=2 (1 -P n )). (12)
Overall, we have shown throughout this subsection that if the service rates µ n of all queues of the high-level model were to be known, then we can easily derive all the key performance parameters of our wireless network.

B. Low-level modeling

In order to estimate the missing parameters of the high-level queueing model, i.e., the mean service times S r n and S l n involved in the derivation of the service rates µ n of all M/M/1/K queues (see relation ( 10)), we associate with each queue and with each direction (left-to-right or right-toleft) a Continuous-Time Markov Chain (CTMC) inspired from Bianchi's original discrete-time model [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF], and describing precisely the transmission process of a node according to the IEEE 802.11 DCF protocol. Therefore, any node n with n = 2, ..., N -1 is associated with two CTMCs, one describing the transmission time of a datagram from node n to node n + 1, and the other one describing the transmission time of a datagram from node n to node n -1. Obviously, since buffers of transmission for nodes 1 and N are only fed by a single flow, we associate a single CTMC with each of these border nodes. Before going further, it is important to emphasize that the original Bianchi's model [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF] could not be used instead of ours as a low-level model for our general framework. We discuss the reasons for this in the Appendix.

We now explain how to use the CTMC to obtain an estimate of the mean transmission time S r n . Note that the estimation of S l n can be performed in an analogous way using the other CTMC associated with the node. We define the CTMC so that it precisely describes the succession of the different states node n has to go through in order to transmit a datagram to node n + 1. The CTMC is depicted in Figure 4 and overall, consists of m lines, each of which corresponding to the backoff time interval preceding the k-th transmission of a given datagram (this implies that the k -1 preceding transmissions of the datagram were in error). Recall that m denotes the maximum number of transmission attempts for a frame. Before describing the expression of all the rates appearing in the CTMC and describing how they can be estimated, let us first assume that the values of all of these rates are known. It is then straightforward to compute the mean transmission time S r n , i.e., the time needed to go from the first DIFS state up to the END state of the CTMC:

DIFS T 1,1 1,W1-1 1,W1 DIFS T 2,1 2,W2 2,W2-1 2,W2-2 DIFS T m,1 m,Wm 7,Wm-1 m,Wm-2 END ctmc.pdf
S r n = t r 1,n + f r n (t r 2,n + f r n (t r 3,n + • • • + f r n t r m,n )) (13)
where f r n = r n r n +δ r n is the loss frame probability (see rel. ( 2) in Section III-B), and t r k,n corresponds to the mean time spent by the process in the k-th line of the CTMC. The main approximation here is that, at each transmission attempt, and regardless of the number of retransmissions experienced, each frame gets lost with constant and independent probability. By construction of the CTMC, we get:

t r k,n = t DIFS + W k 2 r n + T n,n+1 (14)
where T n,n+1 is the mean transmission time of a frame between node n and node n + 1 (see Section III-B), and r n is the average time spent in any pair of loop states ({k, j}, FREEZE) at node n. We can express r n as:

r n = 1 α 1 + β n γ n . ( 15
)
Before going any further, it is very important to point out that one important parameter involved in the derivation of the CTMC is the frame loss probability f r n . As detailed in Section III-B, this probability is related to the frame error rate FER r n and to the collision probability COL r n (see relation [START_REF] Garetto | Modeling media access in embedded two-flow topologies of multi-hop wireless networks[END_REF]).

As discussed above, the CTMC involves several rates that need to be correctly set. Some of them, namely σ i and α, are constant, and they depend neither on node n, nor on direction r.

Other rates, namely δ r n , r n and η r n , depend both on node n and direction r. Finally, the remaining rates, namely β n and γ n , only depend on node n (they do not depend on direction r).

The first set of parameters comprises constant rates that are very simple to estimate from the IEEE 802.11 specifications. σ i is just the product of the inverse of the time spent in state DIFS by a uniform probability deriving from the current size of the contention window:

σ i = 1 t DIFS (W i + 1)
, for i = 1, ..., m.

α is simply the inverse of a slot time duration:

α = 1 t SlotTime . ( 17
)
The second set of parameters consists of rates leaving out of states T, which correspond to frame transmissions. For the first m -1 lines of the CTMC, r n is the rate from T to the next DIFS state, corresponding to an unsuccessful frame transmission. It can thus be expressed as:

r n = f r n T n,n+1 (18)
where T n,n+1 is the mean transmission time of a frame between node n and node n + 1 and f r n is the frame loss probability (see Section III-B). Similarly, δ r n is the rate from T to the END state, corresponding to a successful frame transmission, and can thus be expressed as:

δ r n = 1 -f r n T n,n+1 . (19)
Finally, η r n is the rate leaving out of the last T state, corresponding to the last frame transmission attempt, always leading to the END state (whether the transmission is a success of a failure). It follows that:

η r n = r n + δ r n . (20)
The third set of parameters comprises two types of rates, i.e., β n and γ n , whose estimation is, in general, more difficult. At this stage, we do not include the corresponding generic formulas for these two parameters and just give some intuition on how to derive them. In the next section, we discuss how to instantiate these formulas when considering specific configurations of our wireless network.

The inverse of β n has an easier interpretation than β n itself. It corresponds to the mean time between two successive backoff freezings of node n, conditioned by the fact that node n is in backoff. This quantity is naturally related to the mean backoff duration of node n before any frame transmission attempt, and to the mean number of times the backoff timer of node n is frozen by transmissions of other nodes. The first parameter (mean backoff duration) can easily be related to the frame loss probability, whereas the second one (the mean number of freezes) is much more complicated to estimate, as it depends on the transmissions of all other nodes that are within the carrier sensing range of node n.

Again, the inverse of γ n is easier to interpret, as it corresponds to the mean freezing duration of the backoff of node n. For many cases this quantity merely corresponds to the mean frame transmission time of neighbor nodes (including the returning time of the acknowledgment), and thus is easy to be estimated. However, in more complicated scenarios, frame transmissions of two nodes that are not in the carrier sensing range of each other can overlap, resulting in longer freezing durations.

As a conclusion of this subsection, let us underline that among all the parameters of the two CTMCs associated to node n (in both directions), only three are not easy to estimate since they are not derived straightforwardly from the IEEE 802.11 specifications and systems characteristics.

These are the frame collision probability COL r n (and similarly COL l n ), the rate β n and the rate γ n . In Section V, we show how to estimate them in specific configurations.

C. Fixed-point solution

As stated in the introduction of this section, the solution to the high-level queueing model requires input values for µ n that can be directly derived from the solution of the low-level CTMC.

Conversely, the low-level CTMC models have input parameters, whose values can be derived from the performance parameters of the high-level queueing model, namely X n , D n , U n and P n .

As a result, the overall model can be solved using the fixed-point iterative procedure described by Algorithm 1. The stopping criterion is triggered whenever the deviation for the estimated values of parameters µ n between two successive iterations is less than a given threshold. Once the algorithm has converged, it returns the performance parameters of interest for the network understudy, namely G r , G l , L r and L l .

With the exception of steps 5, 6 and 7, whose instantiation depend on the specific network under consideration, every other step of this algorithm has been described in details in this section and can be applied for any given path.

In the thousands of examples we studied, the fixed-point iteration involved in our solution never failed to converge within typically just a few tens of iterations. The computation at each solve the high-level queueing model and obtain X n , D n , U n and P n for all n = 1, ..., N (rel. ( 3)-( 5)) 4: calculate q r n and q l n for all n = 1, ..., N (rel. (

estimate COL r n and COL l n for all n = 1, ..., N

estimate β n for all n = 1, ..., N

estimate γ n for all n = 1, ..., N

for n = 1 solve the low-level right CTMC associated with node 1 and calculate S r 1 (rel. ( 13))

9:

for n = 2, ..., N -1 solve the 2 low-level CTMCs associated with node n and calculate S r n and S l n (rel. ( 13))

10:

for n = N solve the low-level left CTMC associated with node N and calculate S l N (rel. ( 13))

11:

update µ n for all n = 1, ..., N (rel. ( 10))

12:

update λ n for all n = 1, ..., N (rel. ( 8))

13: until convergence of the algorithm 14: return G r , G l , L r and L l (rel. ( 11)-( 12))

iteration is quite simple so that the resulting execution speed is very fast, i.e., several orders of magnitude faster than a discrete-event simulation. We include more details about the speed of convergence of the method in the Appendix.

V. CASE STUDIES

In order to highlight the versatility of our modeling framework as well as its accuracy, we consider 3 case studies of multi-hop wireless paths that differ by their number of nodes and of flows. For each of these case studies, we detail the modeling aspects specific to the considered case study, and we assess the models accuracy in terms of the key performance parameters of a path. The section ends with two examples for the model exploitation providing, at a very low cost of computation, insights in the behavior of wireless multi-hop paths.

Throughout this section, unless it is explicitly stated otherwise, we use the following parameters. The frame transmissions are performed with the standard parameter values of IEEE 802.11b as reported in Table VIII. To ease the presentation of this section, the links have a constant capacity (physical rate) of 11 Mb/s (i.e., no Rate Adaptation) corresponding to the modulation CCK 11. We consider that all datagrams have a constant size of 1500 bytes. Hence, the transmission time for a frame (with its associate ACK) is identical for all nodes, and we denote it simply by T . The received signal power at each node is computed using a transmission power of 31.6 mW, and an antenna gain of 1 dBi. These latter values match the specifications of the ORiNOCO11b card [START_REF] Xiuchao | Simulate 802.11b Channel within NS2[END_REF]. Using the two-ray ground reflection model, it follows that the ranges of communication and carrier sensing cover 399 and 700 meters, respectively.

To account for the non-perfect physical layer, and the fact that transmission errors are more likely when the distance between two transmitting nodes is large, each link experiences a Bit

Error Rate (BER), whose actual value depends on the distance of the link. The derivation of the BER is based on a relation between the received signal power and the used modulation.

For more details on this computation, the reader can refer to [START_REF] Fiore | [END_REF]. Figure 5 was obtained using the relations given in [START_REF] Fiore | [END_REF] for datagrams of 1500 bytes. It shows the evolution of BER and that of the corresponding FER (Frame Error Rate) as a function of the distance between two communicating nodes. Recall that the FER is derived directly from the BER and the length of frames (see rel. ( 1)). In our examples, the BER rises from 4e -9 to 8e -5 as the distance between two communicating nodes widens from 150 to 399 meters. In the latter case, the FER reaches values close to 60%. To evaluate the accuracy of our model, we compare its performance parameters obtained from an implementation in MATLAB with those delivered by a discrete-event simulator (Network Simulator version 2.35 -ns-2.35 [START_REF] Ns2 | [END_REF]). All simulation results have been performed by generating 100,000 packets at the source node(s). Throughout this section, we define the absolute error of

A. Basic case study

We start by considering a multi-hop path with N = 3 nodes that conveys a single flow travelling from node 1 to node 3 through node 2. Recall that this left-to-right flow of datagrams constitutes the workload for the path, and that the datagrams generation at node 1 follows a Poisson process with a rate Λ r . The positions of the nodes, which determine their carrier sensing and transmission ranges, are such that any node can communicate only with its 1-hop neighbor(s), yet it can sense transmissions from the two other nodes.

Since only two of the three nodes are effectively transmitting frames (node 3 is solely returning ACK), the high-level model comprises two queues. And as all frames belong to the same flow, originating at node 1 and ending at node 3, many quantities, related to the possible existence of a second flow such as X l n , q l n , S l n , are zero here. Hence, relations ( 6), ( 8), ( 10), ( 11) and ( 12) are instantiated as follows:

X n = X r n , G r = X 2 , λ n = X r n-1 , L r = 1 -2 n=1 (1 -P n ), S n = 1 µn = S r n .
As said at the end of Section IV-B, three parameters of our modeling framework were left without formula since they strongly depend on the actual network configuration. We now provide ad hoc formulas for the context of this case study.

COL r

n , which represents the probability that a frame sent by node n to its right-hand neighbor collides with another frame, is virtually zero here since any node can sense each other's transmission. Relation (2) becomes simply: f r n = FER r n . By doing this, we overlook the possibility that two nodes start their transmission exactly at the same time. The corresponding probability has been found to be very low [START_REF] Garetto | Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks[END_REF].

The derivation of γ n is also straightforward. Having in mind that 1/γ n corresponds to the mean freezing duration, i.e., the frame transmission time of another node plus a DIFS time, we have:

1/γ n = T + t DIFS .
Finally, let us consider the case of β n . Here, we resort on the fact that 1/β n is equal to the mean time between two successive backoff freezing, given that node n is in backoff. It follows that: 1/β n = B n /np n where B n denotes the mean backoff duration for a frame of node n, and np n indicates the average number of freezing of the backoff of node n. To give a more comprehensive view on the accuracy of our model, we consider hundreds of examples with different values of buffer sizes, workload levels and nodes positions. For each scenario we compute the error committed by our model. We report in Table II the overall distribution of relative errors for the goodput. The mean error is around 4%, and it virtually never exceeds 10%. Similarly, Table III indicates the distribution of the absolute errors for the datagram loss probability. In average, the error is less than 1%, and only 6% of the hundreds examples led to an error greater than 3%, while none of them exhibit an error exceeding 4%.

B. Extension to account for 2 opposite flows

Our second case study extends the former scenario since we consider an additional flow, originating at in node 3. Thus, the workload consists of 2 independent flows, whose arrival process is Poisson with rates Λ r and Λ l , respectively. The remaining assumptions are the same as before stating, among other things, that the 3 nodes can sense each other's transmissions.

From the standpoint of our model, this case study presents two additional complexities. First, the freezing of the backoff of a node may be caused by the activity of the two other nodes.

Second, node 2 handles datagrams from two distinct flows, so that the corresponding frames will experience different channel conditions for their next hop transmission.

As the 3 nodes are effectively transmitting datagrams, the high-level modeling has 3 queues.

Regarding the low-level modeling, the values of the parameters COL r n and COL l n are zero, while γ n is set to 1/(T + t DIFS ) (see Section V-A for more explanation). The only parameter left to determine is β n . Its computation is performed in a very analogous way to the former case study with a single flow. Indeed, we resort again on the formula 1/β n = B n /np n where B n denotes the mean backoff duration for a frame of node n, and np n indicates the average number of freezing of the backoff of node n.

Since node 2 transmits datagrams belonging to both flows, we adapt the computation of B 2 by simply splitting it in 2 components: For np n , we simply extend the formula presented in the previous section to take into account that two neighbor nodes (and not only one) can interrupt a backoff decrement. Thus, we have:

B 2 = q r 2 B r 2 + q l 2 B l 2 where B
np n = j =n F j
Fn η n . Let us recall that the values of F n are easily obtained as they simply denote the frames throughput of node n and derive directly from the datagram throughput X n . The computation of the non-idle probability for node n, η n , remains identical to the description given in Section V-A.

We study the accuracy of the proposed model for a spectrum of configurations of the path.

With Λ r set to 3.5 Mb/s and Λ l set to 1.5 Mb/s, leading to a total workload of 5 Mb/s, and a buffer size K n of 20 packets at each node, we consider the relative error on the combined goodput G r + G l for values of d 1,2 and d 2,3 ranging from 110 to 390 meters in steps of 10 meters. We represent in Figure 7(a) the corresponding results on the accuracy of our model.

Note that the figure corresponds to hundreds of data points explored, and the surface shown is obtained using an interpolation from a set of scattered data points. We observe that the error is generally less than 3%, and rarely exceeds 6%. The errors reach their maximal value, around 12 or 13%, when the link between nodes 2 and 3 is at its maximal length and thus undergoes a large FER, close to 60%. Additionally, we report in Table IV the distribution of the relative errors computed over close to 800 experiments, as well as the mean error value. In the over 800 examples studied, the relative error remain below 5% in over 90% of the cases explored. The mean error is around 3%.

As for the datagram loss probability L r , we explore the model accuracy for values of K n ranging from 5 to 50 in steps of 5, and for workload values of the flow at node 1, Λ r going from 8 compares the goodput G r and the loss probability L r as delivered by our models with those obtained by simulation for two different levels of workload Λ r . We observe that the deviation between the model and the simulation is very low, typically below 5%. Beside the good accuracy of our model when applied to IEEE 802.11g, we observe that the goodput attained with a workload set to Λ r = 15 Mb/s is less than that with Λ r = 10 Mb/s. This suggests a goodput optimum that we study in the following Section V-D. location of node 2. For instance the gap between the maximum value and the asymptotic value (attained when the workload is close to 4 Mb/s) goes up to nearly 50% for d 1,2 = 10 meters, while it stands around 15% in the case of d 1,2 = 350 meters. Our proposed model allows to find out the optimal value of Λ r as well as the corresponding level of goodput at the expense of a very low computational cost. This knowledge can be useful for control mechanisms (such as admission control and traffic shaping policies) that aim to protect the network from congested and counter-productive states.

Our final example deals with the sizing of buffers. With the exception of some peculiar cases, wireless networks obey the following rule: the larger the buffers, the less datagram losses.

Nonetheless this rule of thumb does not quantitatively assess the gain of having larger buffers, and a fortiori, does not indicate when the marginal gain brought by larger buffers starts to vanish.

Our proposed model can help in addressing these issues. Figure 11 shows that while there is a significant gain in augmenting the buffer size from 5 to 10, there is virtually no gain for L r in equipping nodes with buffer capacities beyond 10 datagrams.

with no code optimization. Having in mind that multi-hop wireless networks can be viewed as a set of inter-dependent multi-hop paths, our future work aims to extend our modeling framework to handle more general topologies.

the state description all freezing states reached by a node as soon as it senses the channel busy.

In Bianchi's model, freezing is implicitly taken into account by considering a discrete timescale with states of variable durations. The completion time of a state represents a decrement in the backoff timer, including potential freezing periods. In addition Bianchi's model assumes saturation of nodes, whereas our high-level model provides the real occupancy of nodes. As discussed in Section IV-B, the goal of the low-level model is to provide an estimation of the mean transmission time of a datagram, i.e., S r n and S l n , corresponding to the average time to go from the first DIFS state to the END state of the chain (see Figure 4). The time spent in the different FREEZE states of the chain is thus essential in the computation of this service time, and highly depends on the estimation of parameters β n and γ n , that in turn depend on the occupancy of other nodes of the path given by the high-level model.

Impact of RTS/CTS in the case of a multi-hop path

Figure 12 shows the attained goodput of a flow with and without RTS/CTS in a four-node path for various levels of workload and a buffer size equal to 20 datagrams. Note that all these values were obtained by simulation. For workload levels below 1.4 Mb/s, there is virtually no difference between using and not using RTS/CTS. Beyond this level of workload, the goodput attained without RTS/CTS steadily and significantly outperforms that with RTS/CTS. This is particularly obvious for large levels of workload where the deviation can be close to one order of magnitude.

Speed of convergence of the fixed-point iterative solution

As discussed in Section IV-C, the solution to the proposed models is found using a fixed-point iteration. We could not find a theoretical proof of convergence of the iterative scheme. However, in the thousands of examples we studied, the fixed-point iteration involved in our solution never failed to converge within typically just a few tens of iterations. Since the computational effort at each iteration is quite limited, the resulting execution speed is very fast, i.e., several orders of magnitude faster than a discrete-event simulation.

We now examine the convergence pattern of our iterative scheme to its fixed-point solution.

Let ∆ denote the absolute value of the difference between the estimated values of parameters µ n between two successive iterations in the course of our fixed-point solution. the successive values of ∆ for one example of each case study studied in Sections V-A, V-B and V-C, respectively. Specific parameters for each example are reported in the caption of Figure 13.

We observe that the decrease in the difference from one iteration to the other, namely ∆, appears to be geometric after the first few iterations. Such a geometric decrease was also found on the many other examples not shown in this paper.

Fig. 1 :

 1 Fig. 1: Example of a multi-hop wireless network with 12 nodes and 3 multi-hop flows.

Fig. 2 : 1 .

 21 Fig. 2: Description of a multi-hop path with N nodes and 2 opposite flows.

model and 2 )Fig. 3 :

 23 Fig. 3: High-level modeling of a given node n.

Algorithm 1

 1 Fixed-point solution for the overall model 1: initialize µ n and λ n for all n = 1, ..., N with non-absurd values 2: repeat 3:

Fig. 5 :

 5 Fig. 5: Evolution of BER and FER as a function of the distance for datagrams of 1500 bytes.

  our model versus the actual values (delivered by ns-2.35) as |model -actual|. The percentage relative error is determined as the ratio 100 × | model -actual | / actual.

Figures 6 (

 6 Figures 6(a) and 6(b), the values delivered by our model are very close to the actual values of goodput G r and of loss probability L r .

  Mb/s (actual) Λ r =3 Mb/s (model) Λ r =6 Mb/s (actual) Λ r =6 Mb/s (model) (b) Loss probability.

Fig. 6 :

 6 Fig.6: Accuracy of the proposed model for the case of a path with 3 nodes and 1 flow of rate Λ r for many positions of the relay node using IEEE 802.11b.

r 2 and B l 2 2 = B 3 and B l 2 = B 1 .

 2221 are the mean backoff durations over the links of distance of d 1,2 and d 2,3 , respectively. Note that, since the BER only depends on the distance, B r The quantities B 1 and B 3 are easily obtained using relation[START_REF] Xu | Effectiveness of RTS/CTS handshake in IEEE 802.11 based ad hoc networks[END_REF].

  (a) Relative error on the goodput.(b) Absolute error on the loss probability.

Fig. 7 :

 7 Fig. 7: Accuracy of the proposed model for the case of a path with 3 nodes and 2 flow of rate Λ r and Λ l for many positions of the relay node, buffer sizes, and workload levels using IEEE 802.11b.

12 Λ

 12 r =10 Mb/s (actual) Λ r =10 Mb/s (model) Λ r =15 Mb/s (actual) Λ r =15 Mb/s (model) (a) Goodput.

  /s (actual) Λ r =10 Mb/s (model) Λ r =15 Mb/s (actual) Λ r =15 Mb/s (model) (b) Loss probability.

Fig. 8 :

 8 Fig.8: Accuracy of the proposed model for the case of a path with 4 nodes and 1 flow of rate Λ r for many positions of node 2 using IEEE 802.11g.

Fig. 9 :Fig. 10 :

 910 Fig. 9: Mean buffers occupancy as a function of the distance between nodes 1 and 2 with K n = 20 and Λ r = 2.5 Mb/s.

Figure 11

 11 depicts the datagram loss probability, L r , for various sizes of buffers K n over a wide range of workload levels Λ r with d 1,2 = 370, d 1,3 = 540 and d 1,4 = 750 meters. The obtained results clearly illustrate the benefit of having larger buffers (at least from the loss probability point of view). More interestingly,

Fig. 12 :

 12 Fig. 12: Impact of RTS/CTS on the attained goodput for the case study with four nodes and one flow with d 1,2 = 100 m, d 2,3 = 200 m, d 1,4 = 750 m, K n = 20.

Fig. 13 :

 13 Fig. 13: Speed of convergence of the point-fixed iteration for various scenarios. For 3 nodes and 1 flow: d 1,2 = 250 m, d 2,3 = 250 m, Λ r = 3 Mb/s, K n = 20. For 3 nodes and 2 flows: d 1,2 = m, d 2,3 = 250 m, Λ r = 3.5 Mb/s, Λ l = 1.5 Mb/s, K n = 20. For 4 nodes and 1 flow: d 1,2 = m, d 2,3 = 300 m, d 1,4 = 750 m, Λ r = 3 Mb/s, K n = 5.

  where W max is an upper-bound on the contention window size. The numerical values of these constants for the IEEE 802.11b and 802.11g protocols are reported in Table VIII of the Appendix. The IEEE 802.11 DCF protocol includes two additional features, namely RTS/CTS and EIFS.

TABLE I :

 I Notation used for the multi-hop path.

  Exitingthe k-th DIFS state, the process is uniformly routed towards any state {k, j} or the transmission state with a rate σ k . From any state {k, j}, it can either reach state {k, j -1} (or transmission state if j = 1) if the channel was sensed idle during a complete slot time, or reach a FREEZE state if the channel has been sensed busy. We denote the corresponding rates by α and β n , respectively. The rate out of any FREEZE state is γ n bringing back the process to the state {k, j} where it came from before entering the FREEZE state.

		σ1		σ1		σ1				1 st backoff stage
	σ1
	δn r	α	α	α	α
	εn r	βn	γn	βn	γn	βn	γn
		FREEZE		FREEZE	FREEZE
									2 nd backoff stage
	σ2	σ2		σ2		σ2		σ2
	δn r	α	α	α	α		α
	εn r	βn	γn	βn	γn	βn	γn	βn	γn
		FREEZE		FREEZE	FREEZE	FREEZE
									m th backoff stage
	σm	σm			σm		σm		σm
	ηn r	α	α		α		α		α
		βn	γn			βn	γn	βn	γn	βn	γn
		FREEZE				FREEZE	FREEZE		FREEZE
	Fig. 4: Low-level modeling of the datagram transmission time at node n towards its right-hand
	neighbor, namely S r n .
	As explained in Section III-A, any transmission attempt starts with a DIFS time and then enters
	a backoff procedure, that can be interrupted anytime the node senses the channel as being busy,
	and ends with a transmission time, that can be either successful and thus leading to the END
	state with a rate δ r

n , or in error bringing the process to the next stage of the backoff with a rate r n . Any state {k, j} refers to the k-th stage of the backoff (k ∈ [1, m]) (i.e., the k-th transmission attempt of the datagram) with a current contention window size equal to j (j ∈ [1, W k ]).

TABLE II :

 II Overall accuracy on the goodput for a path with 3 nodes and 1 flow.

					grr
	Average	<5%	5-10% 10-15% > 15%
	4.12%	93.82% 5.95%	0.23%	0.0

TABLE III :

 III Overall accuracy on the loss probability or a path with 3 nodes and 1 flow.

	Average	<1%	1-2%	2-3%	3-4% >4%
	0.85%	60.0% 10.0% 24.0% 6.0% 0.0%

  Table V presents the distribution of the errors over the many explored examples. Here,

	we observe that the mean error is 1.58% and that it remains below 4% in over 98% of the 250
	examples studied.

TABLE IV :

 IV Overall accuracy on the goodput for a path with 3 nodes and 2 flows.

					grr
	Average	<5%	5-10% 10-15% >15%
	3.05%	90.49% 3.33%	6.06%	0.12%

TABLE V :

 V Overall accuracy on the loss probability or a path with 3 nodes and 2 flows.

	Average	<1%	1-2%	2-3%	3-4% >4%
	1.58%	23.6% 48.4% 21.2% 5.2% 1.6%

C. Extension to account for hidden node problem

In our third case study, we consider a path with N = 4 nodes that forwards datagrams from node 1 up to node 4 through nodes 2 and 3. Two possible versions of IEEE 802.11, namely no examples whose error exceeds 10%.

TABLE VI :

 VI Overall accuracy on the goodput for a path with 4 nodes and 1 flow.

					grr
	Average	<2%	2-5%	5-10%	>10%
	2.73%	35.36% 52.86% 11.78%	0.0

TABLE VII :

 VII Overall accuracy on the loss probability or a path with 4 nodes and 1 flow. turn to the case where the 802.11g version of the IEEE standard (the parameter settings are reported in Table VIII) is used in lieu of 802.11b in the four-node path under study. The link capacities are set to 54 Mb/s, and the buffers at nodes are of length K n = 20. We consider various positions for the node 2 with d 1,2 ranging from 100 to 350 meters. Nodes 3 and 4 are kept constant with d 1,3 = 500 and d 1,4 = 750 meters.Figure

	Average	<1%	1-4%	4-7%	7-10% >10%
	1.49%	36.0% 44.0% 16.5%	3.5%	0.0%
	Finally, we

ACKNOWLEDGMENTS

The authors wish to thank the Associate Editor and three referees for their thorough and constructive review of an earlier version of this paper. This work was supported by ANR research project VERSO RESCUE under the contract number ANR-10-VERS-003.

The computation of B n is based on [START_REF] Abreu | Hierarchical Modeling of IEEE 802.11 Multi-hop Wireless Networks[END_REF]:

t SlotTime [START_REF] Xu | Effectiveness of RTS/CTS handshake in IEEE 802.11 based ad hoc networks[END_REF] where W i is the size of contention window for the i-th transmission of a frame, φ k,n denotes the probability that the transmission of a datagram at node n requires exactly k frames, and Φ n is the mean number of frame transmissions required per datagram at node n. Clearly, φ k,n and Φ n can be derived from the frame loss probability f r n as follows: 1 and Φ n = m k=1 kφ k,n with m denoting the maximum number of transmission attempts.

As for np n , let us recall that the backoff of a given node n is paused whenever any node j in the carrier sense range of n makes a transmission. We designate by F n the frame throughput of node n, which corresponds to its number of frame transmissions per unit of time. Clearly, we have: F n = X n Φ n . Assuming node n has always a datagram to transmit, i.e., is saturated, we have:

XnΦn . In the more general case, where node n is not necessarily saturated, we refine this relation with a corrective factor η n such that: np n = X j Φ j XnΦn η n . This corrective factor amounts to the ratio of time node n is non-idle. This quantity is related to the node utilization U n and it reads as: η n =

Sn-T Sn 1-Un

Un +Sn-T . For more details, the reader can refer to [START_REF] Abreu | Hierarchical Modeling of IEEE 802.11 Multi-hop Wireless Networks[END_REF]. We now study the ability of our model to provide fair predictions for the key performance parameters of a three-node path with a single flow. Figure 6 illustrates the accuracy of the proposed model for two different levels of workload Λ r , as well as for a large range of distances between node 1 and relay node 2. In these examples, the distance between nodes 1 and 3 is kept constant to 500 meters, and the buffers at nodes are of length K n = 20. As shown by version b and version g, are studied. Datagrams are generated at node 1 according to a Poisson process with a rate Λ r . We assume that the communication and carrier sensing ranges of a node cover its 1-hop and 2-hop neighbor nodes, respectively. Therefore, nodes 1 and 4 are exposed to the hidden node problem. Frames sent by node 1 can collide with the acknowledgments (ACK) returned by node 4 (to node 3). For some locations of the nodes, the collision probability can be as large as 30%. Thus, and unlike previous scenarios, we need to take into account the risk of frames collision in our modeling.

We estimate the probability that a frame sent by node 1 will collide with an ACK of node 4 as follows: COL r 1 = HID r 1 + ST r 1 where HID r 1 denotes the probability of collision due to the hidden node, i.e., node 4, and ST r 1 refers to the collision probability because a node within its carrier sensing range, i.e., nodes 2 and 3, finishes its backoff countdown at the exact same time as node 1, and thus simultaneously starts its transmission. Note that this latter decomposition is made possible because it involves two disjoint events. Although the full details can be found in [START_REF] Abreu | Modeling of IEEE 802.11 multi-hop wireless chains with hidden nodes[END_REF], we indicate here that HID r 1 is expressed as the ratio between the duration of a collision and the full period that elapses between two frame transmissions by node 1. The computation of ST r 1 is as follows: 1j =1 (1 -U j /B j ) where j iterates over the nodes within the carrier sensing range of node 1. More details are provided in [START_REF] Abreu | Modeling of IEEE 802.11 multi-hop wireless chains with hidden nodes[END_REF].

As for γ n and β n , there is no specific difficulties associated to this scenario. γ n is computed as previously described. In the case of β n , we rely again on the relation: 1/β n = B n /np n . More precisely, B n is evaluated as in Section V-A, while the computation of np n follows the scheme given in Section V-B.

We study the relative error on the goodput G r with a workload rate set to Λ r = 2 Mb/s and buffers at nodes with size K n = 20 datagrams for hundreds of positions of the two relay nodes. First, we rely on our model to study the behavior of the queue length in the buffer of nodes, Q n . We set the rate of the workload to Λ r = 2.5 Mb/s. Figure 9 describes the evolution of the mean queue length at nodes 1, 2 and 3 as a function of the distance between nodes 1 and 2, d 1,2 . Because of the BER, as the distance d 1,2 grows, the quality of the link between nodes 1 and 2 (resp. nodes 2 and 3) decreases (resp. increases). Therefore, the bottleneck link in the path is gradually shifting. With small values of d 1,2 , i.e., less than 50 meters, the BER for the link between nodes 2 and 3 is very large (more than 60% of frames transmissions fail), and in turn, this latter link tends to become the bottleneck. A queue of datagrams is built up at node 2 (clearly shown by Figure 9 where the mean buffer occupancy is close to 20). For larger values of d 1,2 , say between 60 and 350 meters, the BER is relatively low for all links. However, with the exception of the link between nodes 2 and 3, the two other links are exposed to the hidden node problem and thus experience a slowdown pace of transmission. This is the reason why the queues at nodes 1 and 3 are close to the saturation while node 2 is not. Finally, for d 1,2 larger than 350 meters, the link between nodes 1 and 2 is greatly flawed, and thus it becomes the bottleneck link. Consequently, a large queue is built up at node 1. This first example clearly points out the high sensitivity of a path to the BER of its links, hence making its behavior hardly predictable without a fair performance analysis.

Multi-hop wireless paths are known to undergo their best rate of goodput when the workload is capped under a certain threshold, e.g. [START_REF] Li | Capacity of Ad Hoc Wireless Networks[END_REF], [START_REF] Abreu | Substitution Networks: Performance Collapse Due to Overhead in Communication Times[END_REF]. Our second example focuses on the existence of this goodput optimum and on the associated performance collapse which occurs when the workload is excessive. We compute the goodput G r attained by a four-node path for various values of Λ r and for different positions of node 2, d 1,2 . The corresponding values of G r are displayed in Figure 10. We observe that our proposed model captures this performance optima.

The magnitude of these tipping points (turnaround) widely varies depending on the specific

VI. CONCLUSIONS

In this paper, we consider the performance evaluation of a single multi-hop path (also called chain), based on the IEEE 802.11 DCF. The proposed modeling framework is constructive and versatile, so that it can handle various types of multi-hop wireless paths. Its originality comes from its two-level abstraction: the high-level mostly seeks to mimic the buffer behavior of nodes along the path, while the low-level estimates the delay for transmitting a packet according to the IEEE 802.11 DCF, given the surrounding environment of a node. With only small refinements, we apply the proposed modeling framework on three case studies, which together cover various potential difficulties, e.g., two flows in opposite directions, and topologies where nodes are exposed to the well-known hidden node problem. Scenarios in which a fraction of datagrams may enter or leave the path at intermediate nodes could also be easily handled by simply modifying the dispatching in the high-level model, while keeping unchanged the low-level Markov chain models. We performed thousands of discrete event simulations to assess the accuracy of the derived models for the attained goodput of flows and for the datagram loss probability. It is our conclusion that their accuracy is generally good, and that they capture fundamental phenomena occurring in multi-hop wireless networks such as performance collapse and starvation. Finally, in all the thousands of examples we explored in this section, the fixed-point iteration involved in the solution to the proposed models never failed to converge within typically just a few tens of iterations, which corresponds to an execution time smaller than a second on a standard machine

Difference between the low-level Markov chain model and Bianchi's model

Even if our low-level Markov chain model is inspired from the original Bianchi's model [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF],

it differs from it in many points, and we discuss here why this original model could not be used instead of ours as a low-level model for our general framework. As Bianchi's model, our model aims at precisely describing the transmission process of a node according to the IEEE 802.11 DCF protocol, by developing all possible states a given node can to go through in order to transmit a datagram to one of its neighbor over the wireless channel. However, unlike Bianchi's model, our model is a continuous-time Markov chain model that includes in