X Song

L Leotoing
email: lionel.leotoing@insa-rennes.fr

D Guines

E Ragneau
email: eric.ragneau@insa-rennes.fr

Characterization of forming limits at fracture with an optimized cruciform specimen: application to DP600 steel sheets

Keywords: optimized cruciform specimen, experimental forming limits at fracture, prediction of ductile fracture

whether they are published or not. The documents may come

Characterization of forming limits at fracture with an optimized cruciform specimen: Application to DP600 steel sheets

Introduction

In the automotive industry, advanced high-strength steels (AHSS) are adopted for vehicule safty and fuel economy. DP600 is a type of AHSS steels with high strength, ductility and formability [START_REF] Wang | The limit drawing ratio and formability prediction of advanced high strength dual-phase steels[END_REF][START_REF] Ozturk | Tensile and spring-back behavior of dp600 advanced high strength steel at warm temperatures[END_REF]. The increasing application of DP steels demands in-depth analysis of their forming behaviour for optimal use [START_REF] Ramazani | Failure analysis of dp600 steel during the cross-die test[END_REF]. In the forming process of sheet metals, forming limits are generally defined by localized necking but not ductile fracture. Recently, some researchers [START_REF] Bruschi | Testing and modelling of material behaviour and formability in sheet metal forming[END_REF][START_REF] Silva | Failure mechanisms in single-point incremental forming of metals[END_REF] have proposed that ductile fracture can appear without the occurrence of localized necking in traditional sheet metal forming process or single point incremental forming process. The forming limit curve at necking (FLCN) should be replaced by the forming limit curve at fracture (FLCF) to describe failure of sheet metals [START_REF] Han | A ductile fracture criterion in sheet metal forming process[END_REF][START_REF] Song | Investigation of the forming limit strains at fracture of aa5086 sheets using an in-plane biaxial tensile test[END_REF].

In previous studies [START_REF] Martins | Formability and simulative tests in modern sheet metal forming education[END_REF][START_REF] Isik | Formability limits by fracture in sheet metal forming[END_REF], different traditional tests (for example, single tensile test, bulge test, Nakazima test and hemispherical dome test) are used to construct FLCF. These tests require various specimen geometries if a wide range of strain path has to be characterized. Depending on the test, results can be affected by friction between tools and sample, and by sample bending. In the last few years, the in-plane biaxial tensile test with a dedicated cruciform specimen has been proposed to identify forming limits at necking under linear paths [START_REF] Leotoing | Cruciform shape benefits for experimental and numerical evaluation of sheet metal formability[END_REF] and non-linear paths [START_REF] Leotoing | Investigations of the effect of strain path changes on forming limit curves using an in-plane biaxial tensile test[END_REF]. Recently, with the same specimen shape, this test has also been used to determine the forming limits at fracture [START_REF] Song | Investigation of the forming limit strains at fracture of aa5086 sheets using an in-plane biaxial tensile test[END_REF]. As explained in this previous work, the test is interesting to overcome the drawbacks of the conventional sheet formability tests for determination of forming limits at fracture : no influence of bending, no friction and linear or non-linear strain paths with or without pre-strain can be applied to the material. Nevertheless, investigations of necking or fracture limits with the in-plane biaxial tensile test require the use of a complex specimen shape. Indeed, the specimen geometry, usually a cross specimen, must exhibits a fracture at the central point of the specimen to control the strain path thanks to the displacement imposed on the two perpendicular axes. In [START_REF] Song | Investigation of the forming limit strains at fracture of aa5086 sheets using an in-plane biaxial tensile test[END_REF], an initial sheet thickness of 4mm is necessary to manufacture the cross specimens since a notable thickness reduction is required in the specimen central area to force fracture at the center point. Although specimens of cruciform type have been investigated quite intensively, no standards exist when large deformations are required in the central zone [START_REF] Kuwabara | Advances in experiments on metal sheets and tubes in support of constitutive modeling and forming simulations[END_REF]. In order to control the strain path and to reach fracture whatever the imposed strain path, the specimen shape design must ensure both the maximum strain occurs at the center point and reduce stress concentrations in peripheral regions. Classically, three sensitive areas can be identified in the cruciform specimen geometry: (i) the arms, (ii) the transition zone between two arms, and (iii) the central zone [START_REF] Hannon | A review of planar biaxial tensile test systems for sheet metal[END_REF].

For the design of arms, Prates et al. [START_REF] Prates | A new strategy for the simultaneous identification of constitutive laws parameters of metal sheets using a single test[END_REF] used a tapered arm to lead the strains to the central area of specimen for determining the constitutive parameters. Tapered arms were also used by Abu-Farha et al. [START_REF] Abu-Farha | Cruciform-shaped specimens for elevated temperature biaxial testing of lightweight materials[END_REF] for biaxial tests at elevated temperatures (up to 300 • C) and under quasi-static conditions until facture. It was found that an increase of the tapered angle, in conjunction with a smoothly varying thickness profile, shifts plastic deformation closer to the central gauge area. Kuwabara et al. [START_REF] Kuwabara | Measurement and analysis of differential work hardening in cold-rolled steel sheet under biaxial tension[END_REF] adopted a cruciform specimen with slots in the arms to investigate the work hardening behavior of cold-rolled steel sheet. The seven slots in each arm were made with laser. The authors considered that slots in arms were very effective in making the strain distribution in the gauge section almost uniform. Kuwabara et al. [START_REF] Kuwabara | Measurement and analysis of yield locus and work hardening characteristics of steel sheets wtih different r-values[END_REF] also used this cruciform specimen to study the steel sheet yield locus and work hardening characteristics. The same approach was adopted by Merklein et al. [START_REF] Merklein | Characterization of yielding behavior of sheet metal under biaxial stress condition at elevated temperatures[END_REF] with the definition of six slots in each arm. However, the introduction of the slots results in a reduction of the arm cross-section which becomes more compliant than the central section. As a result, arms deform excessively under load and limit the amount of useful strain in the central zone before failure. To overcome this problem, either the thickness of the central zone should be reduced or multiple layers of the arm should be stacked together so that the comparative rigidity of arms increase [START_REF] Green | Experimental investigation of the biaxial behaviour of an aluminum sheet[END_REF].

For the transition zone between arms, Müller et al. [START_REF] Müller | New experiments for determining yield loci of sheet metal[END_REF] and Banabic et al. [START_REF] Banabic | An improved analytical description of orthotropy in metallic sheets[END_REF] proposed notches to investigate the yield criterion. The results showed that a large zone of homogeneous deformation with relatively high strain (12% for the equivalent strain) before instability was obtained. Abbassi et al. [START_REF] Abbassi | Failure analysis based on microvoid growth for sheet metal during uniaxial and biaxial tensile tests[END_REF] have used a cruciform specimen with a large radius of notch to perform an analysis of instability and fracture during complex loading by addressing the influence of ductile damage evolution in necking process. Two different cruciform specimens were compared by Makris et al. [START_REF] Makris | Shape optimisation of a biaxially loaded cruciform specimen[END_REF]: one specimen with constant arm width and the other one with a spline corner fillet. The equibiaxial loading was considered for the comparison of two shapes. The result of the numerical optimization showed that the second shape leads to higher damage concentration in the center of cruciform specimen.

Considering the design of the central zone, Makinde et al. [START_REF] Makinde | Development of an apparatus for biaxial testing using cruciform specimens[END_REF][START_REF] Makinde | Design of a biaxial extensometer for measuring strains in cruciform specimens[END_REF] have designed two different cruciform specimens: a circular central section with reduced thickness for tests with small strains and a squared central section with reduced thickness and slots in the arms to reach large strains. Tasan et al. [START_REF] Tasan | In-plane biaxial loading of sheet metal until fracture[END_REF] considered that it is not possible to achieve the fracture in the central region by only adjusting the in-plane geometry of the cruciform. Based on finite element simulations, they identified three parameters to be optimized (radius of central zone, final thickness, thickness profile of thinner zone) for a strain localization in the center of the cruciform specimen. When a flat thickness-reduced zone is adopted, the localization initiates at the corner fillet of the thickness reduced zone, as observed in [START_REF] Liu | Identification of sheet metal hardening for large strains with an in-plane biaxial tensile test and a dedicated cross specimen[END_REF]. Lee et al. [START_REF] Lee | A new method for testing formability in sheet metal forming at biaxial tensile state[END_REF] proposed a cruciform specimen to construct the first quadrant of FLD. The central zone was reduced by two steps. The first reduction is a circle and the second reduction is a square with rounded corner and with edges rotated by 45 • relative to the axes of the arms. The results showed that the prediction of FLD with the modified Cockcroft criterion meets well with experiments. Zidane et al. [START_REF] Zidane | Development of an in-plane biaxial test for forming limit curve (flc) characterization of metallic sheets[END_REF] designed a cruciform specimen including a two-step thickness reduction in the central zone to investigate the whole FLCN of AA5086 sheets.

Based on literature, the following rules have to be considered to design a cruciform specimen shape for investigating fracture: (i) the tapered arm helps to shift plastic deformation closer to the central zone; (ii) the slots in arms are very effective in making the strain distribution in the central zone almost uniform. Narrow, multiple and equally-spaced slots are preferable for homogeneous strains; (iii) the increase of the notch depth promotes plastic deformation closer to the central zone; (iv) the thickness reduction of central zone is essential for the onset of fracture at the specimen central point.

In this study, three objectives are pursued. The first one is to design a dedicated cruciform specimen for investigating the forming limits at fracture of DP600 sheet metal with a thickness of 2mm. From previous work about in-plane biaxial tensile tests, some specimen shapes are selected. Their potential to reach large strains at the central point of the specimen is numerically investigated. Based on these numerical results, an optimization of a new specimen shape is performed. The second objective is to validate experi-mentally the suggested shape. Experimental in-plane biaxial tensile tests are done with the optimized cruciform specimen under a wide range of strain path. Following the methodology presented in [START_REF] Song | Investigation of the forming limit strains at fracture of aa5086 sheets using an in-plane biaxial tensile test[END_REF], the experimental forming limit curve at fracture is plotted. The last objective focuses on the capability of three classical ductile fracture criteria to predict the onset of fracture for a DP600 steel. Through a FE model of the cruciform specimen, the three selected fracture criteria are first calibrated from experimental fracture limits of one or two strain paths. Then the numerical model is used to predict the whole FLCF for strain paths ranging from biaxial to uniaxial strain states.

Cruciform specimen design

Re-design of cruciform specimens

Four cruciform specimens reported in literature [START_REF] Tasan | In-plane biaxial loading of sheet metal until fracture[END_REF][START_REF] Lee | A new method for testing formability in sheet metal forming at biaxial tensile state[END_REF][START_REF] Zidane | Development of an in-plane biaxial test for forming limit curve (flc) characterization of metallic sheets[END_REF][START_REF] Liu | Identification of sheet metal hardening for large strains with an in-plane biaxial tensile test and a dedicated cross specimen[END_REF] are selected due to their potential to develop large strains in the central zone. As shown in Figure 1, the original sheet thickness is fixed to 2mm for all the shapes. The length (160mm) is imposed by the space requirements of the test machine. The width of arms (30mm) is re-dimensioned considering the technical specifications of the experimental device (maximum load capacity of 50kN on each axis). The minimal thickness of the central zone is set to 0.75mm. A smaller thickness would cause early fracture due to the small defects produced by the milling process. With this set of fixed dimensions, for each specimen shape, a parametric investigation has been considered to define the best set of values (dimensions of reduced zone, radii, notches, slots) to get large strains in the center and minimize strain localization in peripheral zones.

For specimen 1, the thickness of the circular zone varies along a circle arc profile in the thickness direction. The central zone of the specimen 2 is a two steps thickness-reduced geometry. The shape of the first thickness reduction is a square with rounded corners and with edges rotated by 45 • relative to the axes of the arms, while the shape of the second thickness reduction is a circle with flat bottom. Four tapered arms are also included. For specimen 3, the thickness reduction is devided into two steps. The first step of thickness reduction is a square with edges parallel to arms and the second step of thickness reduction is circular with an arc profile in the thickness direction. Four identical slots are added for each arm. For specimen 4, the thicknessreduced zone is a circle with a flat bottom. Four slots are arranged on each arm around the central zone with different locations for median and outer slots.

Numerical simulation

Based on the selected geometries, four FE models have been defined with the ABAQUS code. Considering the symmetrical properties of specimens, only one-quarter is modeled. The linear tetrahedral solid elements are adopted for the mesh. A refined mesh is defined in the central area. Equibiaxial tensile tests under quasi-static conditions are simulated. The identification of DP600 steel behaviour, subjected to in-plane equibiaxial loadings, was performed in a previous work [START_REF] Liu | Identification of strain rate-dependent mechanical behaviour of dp600 under in-plane biaxial loadings[END_REF] for a strain rate ranging from quasi-static to intermediate strain rate. In [START_REF] Liu | Identification of strain rate-dependent mechanical behaviour of dp600 under in-plane biaxial loadings[END_REF], the hardening law of DP600 was identified for high strain levels which makes reliable the calculation of stress field in the range of limit strains. This point will be essential for the numerical evaluation of ductile fracture criteria. Based on this work, the material constants and models used in the present work are briefly recalled hereafter:

Young's modulus of 200 GPa and Poisson's ratio of 0.3 are considered for the isotropic elasticity. For the plastic behaviour, the associated normal flow rule is assumed and Hill48 yield criterion for plane stress condition is adopted. As shown in Table 1, the parameters of Hill48 yield criterion for DP600 have been calculated from three anisotropic coefficients proposed by Ozturk et al [START_REF] Ozturk | Effects of anisotropic yield functions on prediction of forming limit diagrams of dp600 advanced high strength steel[END_REF]. The general strain rate dependent hardening law on the basis of Ludwick's formulation [START_REF] Liu | Identification of strain rate-dependent mechanical behaviour of dp600 under in-plane biaxial loadings[END_REF] is used:

σ = σ 0 εm 1 + Kε p n εm 2 (1)
The parameters σ 0 , K, n, m 1 and m 2 are given in Table 2. All the numerical results are given at the moment corresponding to a maximum value of major principal strain of 20% on the inside of the specimen. At the same time, fields of both major principal strain and equivalent plastic strain and their evolution along a specified path (path 1 to 4) are analyzed for each specimen (Figure 2 to Figure 5). Figure 2 shows the numerical results for specimen 1. The maximum value of major strain and the maximum value of equivalent plastic strain are located in the arms. From the evaluations of major strain and equivalent plastic strain along path 1, it can be seen that the major strain is higher in the arms (20%) than in the central point (7%). With such a shape, failure will occur in the arms where an uniaxial tension strain state develops. For specimen 2, as observed with strain fields (Figure 3 (a) and (b)) and with the strain evolution along the diagonal path 2 (Figure 3 (c)), a homogeneous strain field is reached in the central region. Unfortunately, the maximum value of major strain (20%) and the maximum value of equivalent plastic strain (20%) are localized at the transition zone of arms (under uniaxial tensile state). At the central point, the maximum value of major strain is 6%. The equivalent plastic strain presents two rapid changes at the transition between two zones with different thicknesses. In this case, the failure will happen at the corner radius between two arms.

For specimen 3 (Figure 4), the maximum value of major strain is reached at the slot tip (under uniaxial stretching). At the same time, an equivalent plastic strain of 18% is reached at the central point under equibiaxial stretching. So for this shape, the fracture will probably initiate at the end of slot (see Figure 4 (c)) where the major strain is higher (20%) than the one at the central point (9%).

Figure 5 shows the numerical results for specimen 4. Both, the maximum value of major strain and equivalent plastic strain are located at the tip of slots. As observed along the path 4, the major strain is much higher at the slot end (20%) than at the central point (7%). Another strain localization Clearly, Figure 4 and 5 show the interest of slots since higher values of maximal principal strain are measured at the central point of the specimen and strain difference between localization points of strains and the central point is minimized.

Optimized cruciform specimen

Based on the above results, a new cross shaped specimen is proposed, as shown in Figure 6. In the thickness direction of the circular reduced zone (radius of 7mm), a circle arc profile is adopted to generate strain localization at the central point. Six slots are defined for each arm and the arrangement of slots is optimized.

As shown in Figure 7, a FE model has been built with 3D tetrahedral elements and a refined mesh in the central area.

Figure 8 shows the numerical results of the optimized specimen. The maximum value of major strain reaches 20% at the slot tip and 18% at the central point of the specimen. At the same moment, a value of 35% of equivalent plastic strain is reached at the central point. It can be seen that the values of major strain and equivalent plastic strain are much higher at the central point than in arms or in transition zones of arms. Therefore, this optimized cruciform specimen shape presents an interesting potential and will be experimentally evaluated in order to plot the whole FLCF of 2mm thickness steel sheets of DP600 grade.

For optimizing the shape of cruciform specimen, a gradual thickness reduction in the central zone is essential to observe strain localization and fracture in the center. Meanwhile, the addition of slots limits high strains in transition zones of arms. This effect is emphasized with a high number of slots. The position of the ends of slots has also to be considered and optimized.

Experimental validation

Biaxial testing machine and strain measurement

As shown in Figure 9, a servo-hydraulic testing machine equipped with four independent dynamic actuators is used. The central area of the cruciform specimen can be deformed under various strain paths when different speeds are used on the two perpendicular axes of the machine. Here, a speed of 1mm/s is used for the two axes to produce the equibiaxial tension state. The digital image correlation (DIC) is adopted to evaluate the surface strain components during the tests. A Fastcam APX-RS camera is adopted to take continuous images and an acquisition of 250 frames/s is used. A random speckle pattern is needed in the DIC method and the plane surface of the non-reduced side of central zone is used to produce the random speckle pattern.

Identification of fracture and necking

Depending on the strain evolution and the surface images of specimen, a time-dependent method is adopted to determine the appearance of fracture and to obtain the forming limit strains at fracture [START_REF] Song | Investigation of the forming limit strains at fracture of aa5086 sheets using an in-plane biaxial tensile test[END_REF]. The equivalent strain field for an area of 2.4 × 2.4 mm in the center is presented in Figure 10 at time 0.004s before fracture. The evolution of the equivalent strain at point A is plotted in Figure 11. As shown in this figure, the macroscopic crack (Figure 12 (b)) occurs with an abrupt change of equivalent strain in a very short time (0.004s). The major and minor strains of the central area at the moment just before the appearance of macroscopic fracture are used as the forming limit strains at fracture. A critical ratio method applied in previous works [START_REF] Leotoing | Investigations of the effect of strain path changes on forming limit curves using an in-plane biaxial tensile test[END_REF][START_REF] Zhang | A comparative study of different necking criteria for numerical and experimental prediction of flcs[END_REF] is used to identify forming limit strains at necking. As shown in Figure 13, when the necking occurs in the central zone (point A in Figure 10), the level the equivalent strain increases abruptly due to the appearance of the plastic instability. Outside the necking zone (point B in Figure 10), the level of equivalent strain stops increase. The equivalent strain increment ratio between point A and point B reaches a critical ratio (value of 4 in this study) for the onset of necking, and the corresponding major and minor strains of point A define the forming limit strains at necking.

Experimental results

As shown in Figure 14, experiments are produced under different strain paths from uniaxial to equibiaxial stretching. The solid markers and dashed lines represent the forming limit strains at fracture and the quasi-linear strain paths, respectively. As show in the above figure, the forming limit strains at fracutre of the DP600 sheet metal are fitted by the Fracture Forming Limit Line (FFL) [START_REF] Isik | Formability limits by fracture in sheet metal forming[END_REF]. The least-square method (Eq. 2) is considered for the fitting process and k=-0.39 and A=0.63 are obtained.

ε major = kε minor + A (2)
Figure 15 shows fractures under different strain paths. For all the strain paths, the initial fracture occurs in the centre of the cruciform specimen and all the cracks are perpendicular to the rolling direction. Figure 16 shows the limit strains at necking and at under different strain paths. The limit strains are higher at fracture than at necking, except for the equibiaxial tension condition. The biggest difference between the FLCF and the FLCN is located near the plane-strain condition. For the equibiaxial tension, three points (A, B and C) in the central area are used to identify the onset of necking, as shown in Figure 17. Figure 18 shows the evolution of the equivalent strains of the three points. It can be seen that there is no saturation of equivalent strain until fracture, neither for the point B or point C. Therefore, no necking occurs under the equibiaxial stretching condition. For this case, the limit strains at fracture determine the deformation achievable. Ductile fracture due to void formation is induced before onset of localized necking. This phenomenon is rather common and was frequently observed for aluminium alloys, as reported by Embury et al. for AA5154 [START_REF] Embury | Formability maps[END_REF] or by Takuda et al. [START_REF] Takuda | Finite element analysis of limit strains in biaxial stretching of sheet metals allowing for ductile fracture[END_REF] for AA5182.

Prediction of the FLCF

Ductile fracture criteria

Three previously published ductile fracture criteria are selected. Different stress tensor invariants (the hydrostatic pressure σ , the maximum principal stress σ max and the equivalent stress σ) are considered within these criteria. One or two parameters need to be identified for each criterion. The classical Cockroft and Latham criterion [START_REF] Cockroft | Ductility and the workability of metals[END_REF] is based on the principal tensile stress, rather than the generalized stress.

∫ εf 0 σ max σ dε p = C 1 (3)
Brozzo et al. [START_REF] Brozzo | A new method for the prediction of formability in metal sheets, sheet material forming and formability[END_REF] proposed a modification of Cockroft and Latham criterion to consider the effect of hydrostatic stress explicitly as follows: The Oyane criterion [START_REF] Oyane | Criteria for ductile fracture and their applications[END_REF] is derived from the equations of plasticity theory for porous materials as follows:

∫ εf 0 2 3 (1 - σ h σ max ) -1 dε p = C 2 (4)
∫ εf 0 ( σ h σ + C 3a ) dε p = C 3b (5)
The fracture will appear when the parameter C i (i=1, 2, 3) reaches a critical damage value.

Numerical results

The damage value C i of each criterion can be calculated at every step of the FE simulation of the cruciform specimen by using the user subroutines. Figure 19 shows the predictive results of forming limit strains with the Cockroft and Latham criterion, by introducing different values of C1 (0.54, 0.57 and 0.72). For the three values of C1, the numerical FLCFs from Cockroft and Latham criterion follow a line shape. With the increase of C1 value, the position of the numerical FLCF changes while the slope keeps almost constant. The solid markers in the Figure 19 correspond to the experimental results identified with the DIC method. These points are fitted by a red line with the least-square method. It can be seen that the slopes of the numerical and experimental FLCFs are quite different. For DP600, the Cockroft and Latham criterion is not able to give a reliable prediction of forming limits, whatever the strain path. A calibration of the C1 value near the plane strain condition will give the best prediction.

The numerical FLCFs calculated by the Brozzo criterion with different values of C2 (0.64, 0.74 and 0.84) are shown in Figure 20. The shape of numerical FLCFs is very different from the one from experimental results. Whatever the value of C2, the limit strains under equibiaxial stretching are significantly underestimated. This criterion is not suitable to predict fracture limits for this material.

Conclusions and perspectives

A summary of designs of cruciform specimen for in-plane biaxial tension test is presented. Based on the numerical results of four redesigned cruciform specimens, an optimized shape is proposed for investigating the forming limits of DP600 sheet metal.

The experimental forming limits at fracture of DP600 sheet metal are determined by the proposed time-dependent method. The forming limit strains are higher at fracture than at necking under different strain paths, except for equibiaxial stretching, for which no necking appears before fracture. The numerical FLCFs with three ductile fracture criteria present various results. The Oyane criterion with two parameters to identify gives the best prediction.

The effect of the strain path change on the forming limit strains at fracture of the DP600 sheet metal will be discussed in future. The influence of unloading during the strain path change will also be considered.

Figure 1 :

 1 Figure 1: Geometries of re-designed cruciform specimens

Figure 2 :

 2 Figure 2: Numerical results of specimen 1

Figure 3 :Figure 4 :

 34 Figure 3: Numerical results of specimen 2

Figure 5 :

 5 Figure 5: Numerical results of specimen 4

Figure 6 :Figure 7 :Figure 8 :

 678 Figure 6: Geometry of optimized specimen

Figure 9 :

 9 Figure 9: The in-plane biaxial tensile machine

Figure 10 :

 10 Figure 10: Equivalent strain field of the central area at the time 0.004s before fracture

Figure 11 :Figure 12 :Figure 13 :

 111213 Figure 11: Identification of fracture

Figure 14 :

 14 Figure 14: Limit strains at fracture of DP600 under different strain paths

Figure 15 :

 15 Figure 15: Fracture of cruciform specimens under different strain paths

Figure 16 :

 16 Figure 16: Comparison of limit strains at necking and at fracture under different strain paths

Figure 17 :Figure 18 :

 1718 Figure 17: Equivalent strain field of the central area at the time 0.004s before fracture under equibiaxial stretching

Figure 19 :

 19 Figure 19: Prediction of forming limits with the Cockroft and Latham criterion, with different values of C1

Figure 20 :

 20 Figure 20: Prediction of forming limits with the Brozzo criterion, with different values of C2

Figure 21 :

 21 Figure 21: Prediction of forming limits with the Oyane criterion, with different values of C3b

Table 1 :

 1 Lankford's coefficient and Hill48 yield parameters

	r 0	r 45	r 90	F	G	H	L	M	N
	0.89 0.85 1.12 0.420 0.529 0.471 1.500 1.500 1.282

Table 2 :

 2 Identified parameters of the rate-dependent hardening law for Hill48 yield criterion[START_REF] Liu | Identification of strain rate-dependent mechanical behaviour of dp600 under in-plane biaxial loadings[END_REF]

	σ 0 (MPa) K (MPa)	n	m 1	m 2
	339.2	839.7	0.3864 0.0052 0.0158


Zidong Su

Bruno Baynat

Thomas Begin

A new model for DPDK-based virtual switches

Keywords: NFV, virtual switch, DPDK, modeling, performance evaluation, polling system, switch-over time

In an SDN/NFV-enabled network, the behavior of virtual switches is a major concern in determining the overall network performance. The prominent open-source solution for virtual switching is Open vSwitch while the DPDK library has been developed to accelerate the packet processing. In this paper, we develop a general framework for the modeling and the analysis of DPDK-based virtual switches, taking into account the switchover times (amount of time needed for a CPU core to switch from one input queue to another). Our model delivers performance metrics such as the buffer occupancy, the loss rate and the sojourn time of a packet in RX queues. We compare our new model with two existing models. Numerical results show that our model combines the accuracy of one model and the efficiency of the other.

I. INTRODUCTION

The softwarization of networking is profoundly reshaping the landscape of telecom and computer networks. ICT industries envision costs optimization through a better management of their resources and a faster deployment of their services. Two technologies are key enablers to this end. First, Softwaredefined networking (SDN) outsources all the decision-making networking functions into a (set of) controller(s) in charge of determining how to handle the incoming traffic. Hence, networking devices, such as routers, load balancers, and firewalls are replaced by appliances receiving their instructions directly from the controller(s) (using a standard interface like OpenFlow [START_REF] Mckeown | OpenFlow: enabling innovation in campus networks[END_REF]). These appliances can thus be reprogrammed at will by the controller(s). Second, Network function virtualization (NFV) refers to the gradual move of network functions out of dedicated hardware devices and into software. Routers, firewalls, load balancers and other networking devices are then running virtualized on commodity hardware, like a standard x86 server. Therefore, in an SDN/NFV-enabled network, the nodes forwarding, filtering or performing other advanced operations on the traffic are typically referred to as virtual switches because they are software-implemented and not deciding the rules.

The network programmability combined with the softwarization of its functions allows a greater extent of flexibility in the way network operators handle their resources. A good case in point is the dimensioning of a network. Instead of the usual overprovisioning strategy, an operator will scale up and down its resources as the demand varies. For instance, when more bandwidth is required on a virtual switch, additional physical resources, e.g., CPU cores, can be provisioned to take part of the load.

In a 2016 paper, Artero et al. [START_REF] Gallardo | Performance modeling of virtual switching systems[END_REF] describe an analytical model for virtual switches based on the decomposition of the switch into several poling systems, each one being decomposed into simple Markov chains. Presented as a first step towards a more general model, this work assumes a negligible switch-over time (time spent by a CPU core to switch from one input queue to the next one). In [START_REF] Sohail | Performance evaluation of a non-exhaustive polling system with asymmetrical finite queues[END_REF], Sohail presents another possible model that takes into account the switch-over time, but that relies on the analysis of multi-dimensional Markov chains, resulting in a time-consuming algorithm. The objective of the current paper is to combine the simplicity of the first model and the ability of the second one to take into account switch-over times. To this end, we develop a general framework that first decomposes the virtual switch into several poling systems and then subsequently decompose each polling system into several queueing systems with server vacation. The two pre-cited papers, as well as the current paper, fall within the scope of this framework, and differ by the way the vacation is represented and the corresponding queueing system is analyzed.

The remainder of the paper is as follows. In Section II, we describe the internal architecture of a virtual switch. Section III describes our new proposed model. Section IV covers the numerical results that validate our model accuracy. Section V concludes this paper.

II. SYSTEM DESCRIPTION

A. Virtual switches solutions

In SDN/NFV-enabled networks, virtual switches are in charge of the data plane. They are software implemented and designed to run on commodity hardware, either directly on the appliance or, more commonly, in a virtual environment. Therefore they may have to share physical resources with other virtual machines (VMs) running on the same appliance. Following rules received from the SDN controller(s), virtual switches basically commute incoming packets between their (physical or logical) ports. They may also perform other operations like filtering, headers editing, and encrypting. A couple of proprietary virtual switch solutions have been released; e.g. by Cisco (Nexus 1000V) and VMware (vSphere Distributed Switch). In the open-source domain, the most prominent solution is Open vSwitch (OvS) [START_REF]vSwitch -An Open Virtual Switch[END_REF]. Although OvS works in Linux hypervisors such as Xen and KVM, and is integrated into OpenStack [START_REF]OpenStack[END_REF], virtual switches performance are usually seen a bit low for commuting very high rates of packets. Hence several techniques, e.g., Netmap [START_REF]Netmap[END_REF], OpenOnload [START_REF] Openonload | [END_REF], PacketShader [START_REF] Packetshader | [END_REF] and DPDK [START_REF]Data Plane Development Kit (DPDK)[END_REF], have been developed to provide a faster packet processing. In this paper, we focus more specifically on the DPDK library [START_REF] Pongrácz | Removing roadblocks from SDN: openflow software switch performance on intel DPDK[END_REF].

B. Internal architecture

Hardware-wise, a virtual switch includes RAM, several I/O ports, and a set of (physical or logical) CPU cores. If DPDK is enabled, each core polls cyclically all the ports, as illustrated by Figure 1.

Upon arrival on a port, packets are immediately dispatched in separate queues, called RX queues. This dispatch aims at spreading evenly the load among the RX queues. This first step is typically carried out using a hash function on the packet headers (e.g., Receive Side Scaling). On the other hand, each core is assigned to a single RX queue of each port (so that a core handles as many RX queues as the number of ports in the virtual switch). It follows that the total number of RX queues is thus equal to the product of the number of cores by the number of ports. When a core starts polling an RX queue, it processes the first-in-line packet, if any, (or the M -first if the batch mode is enabled) before moving to the following RX queue. We denote the time taken by a core to switch from its current RX queue to the next one as the the switch-over time.

From the standpoint of cores, a core processes packets from various RX queues in a polling fashion, as depicted by Figure 1. To complete the processing of a packet, a core needs at least to read (and edit) its headers, extract the destination address, and find out to which output port the packet must be forwarded. The processing task can include additional steps like flowspecific operations (e.g., deep packet inspection, encryption, QoS monitoring). Afterward, the packet is (logically) forwarded from its RX queue to the TX queue associated to the appropriate output port. From this time on, the packet is simply waiting for its transmission on the next link.

Given the current transfer rates of SDRAM and the data rates of communication links, the bottleneck of a virtual switch, if any, lies in the packet processing steps. Hence, we concentrate our modeling efforts on the interactions between the CPU cores and the RX queues.

C. System notation

We conclude this section by introducing notation used throughout this paper. We denote by C the total number of allocated (physical or logical) CPU cores. We let N represent the number of ports attached to the virtual switch. We use Λ i to denote the packet arrival rate on each port i (i = 1, . . . , N ) paquet being served Fig. 2. Subsystem a single CPU core polling several RX-queues. while λ j i refers to the rate of packets dispatched to the jth RX queue of port i, and hence handled by the j-th core

(j = 1, . . . , C). It follows that Λ i = C j=1 λ j i .
Each RX queue has a finite capacity limiting to K the maximum number of packets being simultaneously queued in it. We use µ j i to denote the processing rate of the j-th core when it is serving the i-th RX queue. In other words, 1/µ j i represents the average time the j-th core needs to process a packet from the i-th RX queue. Finally, we denote by 1/β the switch-over time taken by a core to switch from its current RX queue to the next one (β is thus the switch-over rate). Note that these latter quantities are directly measurable on a virtual switch.

III. MODEL

A. Decomposition principle

The first step of the model is to break down the general switch architecture into C independent subsystems, each of them consisting of one CPU core that polls N independent RX queues. Every subsystem is identified with a distinct color in Figure 1 and is simply referred to as a polling system. In the rest of the paper we only consider the model associated with a given CPU core j and its N related RX queues. Therefore, for the sake of clarity, we drop superscript j in all subsequent notations and equations. Figure 2 represents the polling system associated with the considered CPU core having a service rate µ i when serving its i-th RX queue, and a switch-over rate β.

The idea is to subsequently replace each polling system with a set of N independent queueing models with server vacations. This decomposition step is illustrated in Figure 3. The buffer of queue i in the decomposed model represents the i-th RX queue associated with the considered CPU core. The server of the i-th queue in the decomposed model aims at reproducing the way packets of the i-th RX queue are processed by the CPU core. Because the core polls all its RX queues in-between the processing of two successive packets of a given queue i, there is an in-between time that corresponds to the processing of one packet at all the other non-empty queues and N switch-over times. In the model, this total time will be referred to as a vacation time. As an illustration, in Figure 3, the server of queue N is in process, meaning that the CPU core is currently processing a packet in RX queue N , and all other queues are in vacation. In this particular example, when queue N ends its processing, it goes in vacation, the first in-line packet of queue N is put on a hold, and at the same time the switch-over time between RX queue N and RX queue 1 starts. It is only after the completion of this switch-over time that queue 1 ends its vacation and starts the processing of its first in-line packet. Instead of developing, as in Sohail model [START_REF] Sohail | Performance evaluation of a non-exhaustive polling system with asymmetrical finite queues[END_REF], the vacation time as the whole succession of switch-over and processing times, we keep in the vacation time the first switch-over time and aggregate all the remaining phases. The idea is illustrated in Figure 4. Following the processing stage of the server, the vacation starts by a switch-over time between RX queue 1 and RX queue 2. The remaining of the vacation time is then aggregated into a single phase with a given rate α 1 (i.e., with a given mean duration 1/α 1 ), that has to be accurately estimated.

B. Markov chain

In order to derive a tractable model, we make the following Markovian assumptions. First, we assume that the arrival of packets at the entrance of queue i follows a Poisson process of rate λ i . Then, we assume that the processing time of one packet from queue i is exponentially distributed with rate µ i . Finally, we assume that both phases of the vacation time of queue i are exponentially distributed with rates β and α i , respectively.

Under these assumptions can with each queue i of the decomposed model, the continuous-time Markov chain depicted in Figure 5. A state (k, P ) of this chain, k = 1, . . . , K, corresponds to queue i with currently k packets and the first-inline packet being processed (P), i.e., the CPU core is assigned to RX queue i. A state (k, S) of this chain, k = 0..., K, corresponds to queue i with k packets, in which the CPU core is not anymore processing a packet but is switching (S) between RX queue i and RX queue i+1. Finally, a state (k, V ) of this chain, k = 0..., K, also corresponds to queue i with k packets, but now the CPU core is either processing another RX queue or switching between the other RX queues.

From any state of this chain (except for the right ones corresponding to a full buffer) we can reach the state immediately on the right with some rate λ i corresponding to the arrival of a new packet in queue i. We can exit a state (k, P ), k = 1, . . . , K, after a processing time of rate µ i taking the chain to state (k -1, S), and we can exit a state (k, S), k = 0..., K, after a switch-over time of rate β taking the chain to state (k, V ). Now, as defined above, the exiting rate of any state (k, V ) by the end of a vacation is α i . Exiting a state (k, V ) with k > 0 corresponds to the CPU core returning to RX queue i and then processing the next-in-line packet, i.e., coming back to state (k, P ). Now, exiting state (0, V ) corresponds to skipping a turn for RX queue i. Indeed, although the core becomes available for RX queue i, this latter has no packet to be processed. This corresponds to the transition from (0, V ) to (0, S).

1,P 2,P 3,P 0,S 1,S 2,S 0,V 1,V 2,V K-1,P K,P K-1,S K-1,V K,S K,V λ i λ i λ i λ i λ i λ i λ i λ i λ i μ i μ i μ i μ i α i α i α i α i α i β β β β β ... ...
In order to solve this chain corresponding to a particular queue i, only one parameter remains to be estimated, namely α i (the other parameters λ i , µ i , β, and K are supposed to be known from measurements on the system). However, assuming that α i is known, we can easily check that this Markov chain can be solved without resorting to any numerical technique. As a result, solving a Markov chain of our model is as easy (in terms of computational complexity) as solving a Markov chain of Artero et. al model [START_REF] Gallardo | Performance modeling of virtual switching systems[END_REF].

C. Estimation of the chain parameters

Instead of considering α i , we estimate 1/α i , corresponding to the mean time between the end of switching from i-th to (i + 1)-th RX queue (marking the time when the core is leaving queue i) and the end of switching from (i -1)-th to i-th RX queue (marking the time when the core is returning to queue i). Therefore, this time includes N -1 switch-over times, but also includes the processing of one packet for all non-empty RX queue j different from i. It follows that:

1 α i = (N -1) × 1 β + j =i (1 -E j ) × 1 µ j (1)
In this expression, E j represents the probability that RX queue j is empty when the core is returning to it, i.e., at the particular instant when the switch-over time from (j -1)-th to j-th RX queue ends. This parameters can be extracted from the Markov chain associated with RX queue j (equivalent to the one represented in Figure 5 but where i is replaced by j).

Indeed, E j can be expressed as the ratio between the number of transitions from state (0, V ) to state (0, S) by unit of time, and the total number of transitions from red states by unit of time, each of them correspondonding to the end of a vacation for RX queue j. Therefore, we have:

E j = π j (0, V )α j K k=0 π j (k, V )α j = π j (0, V ) K k=0 π j (k, V ) (2)
where the π j are the stationary probabilities of the j-th Markov chain. Not surprisingly, the parameters of a Markov chain associated with a given queue i depend on the stationary solution of the other Markov chains (through Eq. 1 and 2). As a result, the resolution of the model relies on a fixed-point iterative technique that is summarized by Algorithm 1. The main loop of the algorithm is repeated until a given convergence criterion is reached, e.g., the maximum relative difference of varying parameters between two successive iterations is very small.

Algorithm 1: Fixed-point iterative technique

Input : System parameters K, µi, λi, β for each queue i Initialize πi, Ei for each queue i; while convergence criterion not satisfied do foreach queue i ∈ [[1, N ]] do Compute αi using Eq. 1;

Solve the Markov chain associated with queue i and compute the stationary probabilities πi; Compute Ei using Eq. 2; end end Compute all performance metrics of interest;

D. Performance parameters

After convergence of our algorithm, we can derive the system performance parameters from the stationary probabilities of the Markov chains as follows. The average number of packets in queue i is given by:

qi = K k=1 k × (π i (k, P ) + π i (k, S) + π i (k, V )), (3)
As for the loss rate at the entrance of queue i, we obtain:

b i = π i (K, P ) + π i (K, S) + π i (K, V ). (4)
The average sojourn time of an accepted packet in queue i is then obtained using Little's law [START_REF] Allen | Probablity, Statistics and Queueing Theory with Computer Science Applications[END_REF]:

ri = qi λ i (1 -b i ) . (5)

IV. NUMERICAL RESULTS

Throughout this section, we validate the analytical results with a home-made discrete-event simulator. Each simulation is run for 50 seconds of simulated time, which corresponds to the completion of millions packets. that the corresponding confidence intervals are typically very small and hence not displayed in the subsequent figures. In addition to the simulator, we also include, where relevant, results from two existing models: Artero et al. [START_REF] Gallardo | Performance modeling of virtual switching systems[END_REF] and Sohail [START_REF] Sohail | Performance evaluation of a non-exhaustive polling system with asymmetrical finite queues[END_REF].

For the sake of clarity, throughout this section we express the switch-over time as a fraction of the time needed by a CPU core to process a packet. For instance, for a core processing packets at rate µ = 1 Mpps (corresponding to a mean processing time 1/µ = 1 µs), and a switch-over time 1/β = 0.1 µs, the overhead of the switch-over time amounts to 10%.

A. Model accuracy

This section opens with an assessment of accuracy for our new model under various settings of load and switch-over time. We consider a virtual switch with homogeneous CPU cores and a total of N = 5 ports. As discussed in Section III-A, we only focus on a given subsystem involving a single CPU core polling several RX-queues. The processing rate of the core when poling RX queue i is set to µ i = 1 Mpps with i = 1, . . . , 5, while the overhead due to the switch-over time amounts to 10%. Each RX queue has a finite capacity of K = 128 packets. As for the load, we let the total packet arrival rate (Λ = N i=1 λ i ) vary from a low value of 0.5 Mpps to a high value of 3 Mpps. However, ports are unevenly loaded. Specifically, ports 1, 2, 3, 4 and 5 capture 10%, 15%, 20%, 25% and 30%, respectively, of the total load (i.e., λ 1 = 0.1Λ, λ 2 = 0.15Λ, λ 3 = 0.2Λ, λ 4 = 0.25Λ, and λ 5 = 0.3Λ).

Figure 6 shows the performance parameters associated with each port of the virtual switch as found by our new model, the simulation and Sohail model. Figure 6(a) depicts the average queue size (i.e., the number of packets being buffered in RX queues) as a function of the load. As expected, possible values range from 0 to 128, and the 5-th port (depicted in black) receiving the greater fraction of the load is the first to saturate when load increases. It is worth noting that curves are significantly steep revealing a high sensibility to the load. In Figure 6(b) we show the loss rate (i.e., the blocking probability) undergone by each port for increasing levels of load. We observe that losses start to appear for a total load near 0.9 Mpps (while the core is able to process packets at a speed of 1.0 Mpps). This gap is of course due to the non-zero value of the switch-over time. Finally, Figure 6(c) reports the evolution of the average sojourn time spent by a packet in its RX queue. Note that, under a heavy load, the average sojourn times of each port converge to a limiting value given by ((K -1)N + 1)(1/µ + 1/β) = 699.6 1 µs. Overall, Figure 6 shows the good accuracy of both models (ours and Sohail) as both closely match values found by the simulation.

We now study more specifically the accuracy of our new model for various levels of the switch-over time. To this end, we focus on the behavior of a single port (the 3rd) from the previous example. We consider switch-over times ranging from a very low overhead representing 0.1% of the average packet processing time, to a heavy overhead of 10%.

The results are reported in Figure 7, which represents the average size of the corresponding RX queue as a function of the load for several switch-over time overheads. First, we observe that the switch-over time can have a huge impact on the queue behavior: its saturation occurring 10% sooner when the switchover time is high. Second, when the switch-over time is as small as 0.1% of the processing time, its footprint is virtually null. Interestingly, under these circumstances, the results found by our new model precisely match those brought by Artero et al. model (which was designed to handle only examples with no switch-over time). Last but not least, Figure 7 also illustrates the good ability of our model to evaluate the average size of RX queues over a large and realistic spectrum of switch-over times as its values and those delivered by the simulator almost coincide. Note that we obtained similar accuracy for other performance metrics, not shown here for the sake of brevity. Fig. 6. Accuracy on the behavior of RX queues for a virtual switch with N = 5 ports loaded respectively with 10%, 15%, 20%, 25% and 30% of the traffic.

B. Model complexity

We now examine the complexity of our new model. Its memory requirement is very small as the number of states in the Markov chains grows in O(KN ) like in Artero et al. model but unlike Sohail model where it goes in O(KN 2 ).

To describe its computational complexity, we proceed in two steps: (i) we evaluate the number of iterations, and (ii) we evaluate the cost of each iteration. Unlike Sohail model, each iteration of our model involves a finite and known number of simple mathematical operations, which is in O(KN ). However, as often when dealing with a fixed-point solution, the number of iterations cannot be analytically determined. Therefore, we report in Table I the number of iterations to convergence for a growing number of ports, N (using the example described in Section IV-A with a convergence criterion equal to 10 -9 ). This table shows that the number of iterations typically lies in the several tens. Furthermore, it grows only slightly with the number of ports and tends to stabilize around 50 when the number of ports exceeds 8.

Thus, in practice, our model is much faster to run than Sohail model. The difference is particularly marked when the number of ports is large.This is confirmed by V. CONCLUSIONS This paper deals with the modeling of a virtual switch architecture taking into account the switch-over times (amount of time needed for a CPU core to switch from one queue to another). We not only develop a new model, but we also propose a general framework that can be applied to estimate the performance of very general virtual switches. The contributions of the current paper are the following. First, we link together previous papers by showing that they fall within the scope of this general framework. Second, we use this framework to enhance the accuracy of previous models. Third, we propose a new model that accounts for switch-over times but that remains both computationally efficient and accurate. Future works aim at extending our model to the processing of batches of packets.

Fig. 1 .

 1 Fig. 1. Internal architecture of a virtual switch with N ports and C cores.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Decomposition of a sub-system into N separate queues.

Fig. 5 .

 5 Fig. 5. Continuous-Time Markov Chain associated with queue i.

Fig. 7 .

 7 Fig. 7. Accuracy on the behavior of an RX queue for different overhead values of switch-over times, 1/β.

  Figure I which represents the execution time for both model as a function of the number of ports. Unlike Sohail model whose execution time can exceed several tens of seconds, our model, like Artero et al. model, is solved at a click-speed, regardless of the number of ports.

TABLE I NUMERICAL

 I BEHAVIOR OF OUR MODEL. ms) of our model 26 88 165 230 342 467 Execution time (ms) of Sohail model 317 934 1,857 3,077 6,740 12,014

	Number of of ports, N	2 4	6	8	12	16
	Number of iterations of our model 30 43 48	50	52	53
	Execution time (


Marija Stojanova
email: marija.stojanova@ens-lyon.frthomas.begin@ens-lyon.franthony.busson@ens-lyon.fr

Thomas Begin

Anthony Busson

    Conflict graph-based Markovian model to estimate throughput in unsaturated IEEE 802.11 networks Marija Stojanova, Thomas Begin, Anthony

I. INTRODUCTION

WLANs (Wireless Local Area Networks) have become ubiquitous in our everyday life. Internet service providers increasingly employ WLANs to connect users to their network. WLANs are also widespread in airports, train stations, shopping malls, and cities that offer wireless Internet access to their customers. Most WLANs are based on IEEE 802.11 standards. Despite continuous improvements of 802.11 and amendments in its subsequent versions, 802.11-based networks typically feature transmission ranges and data rates that may both be deemed small given the soaring amount of end-users.

These concerns have been largely accommodated by network densification, which refers to the deployment of more APs (Access Points) per unit of area. By doing so, WLANs have improved their spatial reuse of the spectrum, as well as their their transmission rate. However, the management of what used to be a single AP with a few users has become much more complex. WLANs with several APs and tens of users are prone to misconfiguration and poor coordination between APs. Possible effects include inefficient use of the WLAN radio resources, poor overall WLAN performance, and unfairness among users.

Nowadays, WLANs with several APs are increasingly centrally managed to allow for a better use of their resources (e.g., channel allocation, assigning users to the APs, authentication). Besides proprietary solutions, standardized protocols like IETF's CAPWAP and IEEE 802.11v have been developped. These latter enable the exchange of information about the network topology and radio environment (within a WLAN) either from APs to a central controller, in the case of CAPWAP, or between users and APs, in 802.11v. However, the algorithms run by the controller and APs, and exploiting this knowledge, are yet to be designed. Their objectives are diverse and can range from estimating the actual throughput of APs given the network topology to reshuffling the channel allocation scheme. Note that the design of efficient algorithms must cope with the complexity brought by the CSMA/CA scheme used in the 802.11 MAC layer (e.g., random backoff, hidden node problem, starvation).

In this paper, we propose a Markovian, conceptually simple, and computationally efficient modeling approach to discover the behavior of each AP within a WLAN. More specifically, our approach returns an accurate estimation of the output rate (attainable throughput) of each AP given their respective load and the WLAN topology (conflict graph). The outcomes of our approach are manifold: gaining insight into an abnormal WLAN behavior, predicting WLAN performance under new settings, or reconfiguring an existing WLAN. We illustrate two possible applications where we rely on our model to make a better use of WLAN resources.

The rest of this paper is organized as follows. The next section briefly reviews the existing related works. Section 3 describes the system under study. The proposed modeling approach and the associate algorithm are presented in Section 4. Numerical results validating our approach and illustrating possible applications are discussed in Section 5. Finally, Section 6 concludes this paper.

II. STATE OF THE ART

In the last two decades, the performance analysis of the Distributed Coordination Function (DCF) used in IEEE 802.11 wireless networks has been an often revisited topic. Two of the pioneering papers in the field are the works of Bianchi [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF] and Cali, Conti, and Gregori [START_REF] Cali | IEEE 802.11 wireless LAN: capacity analysis and protocol enhancement[END_REF]. Both of them model the network at a very fine level of abstraction, taking into account the behavior of each individual packet transmission according to the CSMA/CA principles. In [START_REF] Cali | IEEE 802.11 wireless LAN: capacity analysis and protocol enhancement[END_REF], the authors study the ratio of the average packet size and the average time it takes to transmit a packet, including all the protocol overhead. They apply this approach to study the utilization of the network's capacity for different numbers of contending stations and packet sizes.

Bianchi [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF] introduces a two dimensional Markov chain to explicitly model the backoff process happening before each transmission of a packet in DCF in a fully-connected network (in which at most one node can be transmitting at a given time). A common property of these two models is that they were designed to handle only saturated networks. In a saturated network, all nodes have a packet waiting to be sent at all times, i.e., they have backlogged queues. Although saturation is a strong and often limiting assumption, these two works provide some of the ground research in the evaluation of wireless networks.

Bianchi's work has since been extended to non-saturated networks using a few different methods. Felemban and Ekici [START_REF] Felemban | Single hop IEEE 802.11 DCF analysis revisited: Accurate modeling of channel access delay and throughput for saturated and unsaturated traffic cases[END_REF] have removed the condition of saturation by introducing the probability that a node has a packet waiting to be sent. To this aim, they create a second Markov chain, which is embedded into Bianchi's original chain [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF]. This embedded chain describes the current state of the channel, which can be either idle, in collision, or in successful transmission. The solution to their model is found by successively iterating between the two chains. Upon convergence, the found solution delivers the steady state transmission probability for each node, which can then be used to evaluate the network's performance.

A different approach for relaxing the saturation constraint is given in [START_REF] Kosek-Szott | A comprehensive analysis of IEEE 802.11 DCF heterogeneous traffic sources[END_REF] and [START_REF] Gupta | New analytical model for non-saturation throughput analysis of IEEE 802.11 DCF[END_REF], where a new state is added to Bianchi's Markov chain in order to represent a node that has an empty buffer. Similarly to Bianchi's original work, the scope of application for these two models is restricted to fullyconnected networks. Note that Kosek-Szott's model [START_REF] Kosek-Szott | A comprehensive analysis of IEEE 802.11 DCF heterogeneous traffic sources[END_REF] can also be used when users have heterogeneous traffic demands, creating a coexistence of low and high traffic densities inside the network.

In all these works, a fine-grained point of view of the network was taken, with a detailed description of each node. Another approach consists in evaluating the performance of a network from a higher level of abstraction. Two such models, that address non-saturated, multi-hop networks, are given in [START_REF] Shi | Analytical models for understanding space, backoff, and flow correlation in CSMA wireless networks[END_REF] and [START_REF] Begin | Performance analysis of multi-hop flows in IEEE 802.11 networks: A flexible and accurate modeling framework[END_REF]. In a multi-hop network, a packet from node A travels across relay nodes before arriving at its destination node B (as opposed to single-hop networks, where A and B directly exchange packets). Both papers present two-level modeling approaches of unsaturated multi-hop wireless networks, in which the low-level model is a version of Bianchi's original Markov chain, while the high-level model aims at capturing the inter-node dependencies in the network. The solution to the overall model is found using a fixed-point iteration between the high and low levels. In [START_REF] Begin | Performance analysis of multi-hop flows in IEEE 802.11 networks: A flexible and accurate modeling framework[END_REF], the high-level model consists of a set of M/M/1/K queues, where each queue represents a given node of the network. Although their modeling framework was designed to handle any number of nodes, examples shown in their paper involve multi-hop wireless paths with at most 4 nodes. In [START_REF] Shi | Analytical models for understanding space, backoff, and flow correlation in CSMA wireless networks[END_REF], the high-level model is a separate Markov chain describing the channel's behavior depending on the current states of neighboring nodes, with nodes being either idle, transmitting, or in backoff. Because of the three possible states for each node and the added complexity brought by multi-hop networks, the analytical model of [START_REF] Shi | Analytical models for understanding space, backoff, and flow correlation in CSMA wireless networks[END_REF] leads to a large state space as the number of nodes increases, making it intractable, for networks with more than 7 or 8 nodes, for which a decomposition into smaller networks is necessary.

In [START_REF] Nardelli | Closed-form throughput expressions for CSMA networks with collisions and hidden terminals[END_REF]- [START_REF] Jiang | A distributed CSMA algorithm for throughput and utility maximization in wireless networks[END_REF], Markov chains are used to model an entire network based on its topology. The states of the chain describe the set of nodes that are transmitting in the current network state. Nardeli and Knightly [START_REF] Nardelli | Closed-form throughput expressions for CSMA networks with collisions and hidden terminals[END_REF] rely on their proposed Markov chain to derive a model that takes into account the errors due to collisions and hidden terminals for a single-hop network. They come up with a closed-form multi-parameter expression of throughput, which is subsequently used for evaluating the performance of the considered network. Although the model accurately captures the behavior of CSMA/CA networks, it only deals with saturated networks and introduces some complexity due to the calculation of successful transmission probability. In [START_REF] Durvy | Self-organization properties of CSMA/CA systems and their consequences on fairness[END_REF], a similar Markov chain is used to evaluate the fairness and spatial reuse in multi-hop, saturated networks with different carrier sensing and reception ranges. More particularly, the authors study the spatial reuse in line-networks to show that CSMA/CA achieves maximal spatial reutilization as traffic intensity increases, at the cost of creating starvation in certain links. In [START_REF] Boorstyn | Throughput analysis in multihop csma packet radio networks[END_REF], [START_REF] Wang | Throughput modelling and fairness issues in CSMA/CA based ad-hoc networks[END_REF] CSMA/CA networks are modeled as continuous time Markov chains and the model is then used to study the fairness of the network. Jiang and Walrand [START_REF] Jiang | A distributed CSMA algorithm for throughput and utility maximization in wireless networks[END_REF] extend the usage of this model by proposing an adaptive solution that changes the nodes' backoff periods in the goal of maximizing the network's throughput and utilization.

A novel approach to modeling a non-saturated network is introduced in [START_REF] Laufer | The capacity of wireless CSMA/CA networks[END_REF] and [START_REF] Kai | Throughput analysis of CSMA wireless networks with finite offered-load[END_REF], where the authors have chosen to map the idle time of a node to a longer backoff period. This approach keeps the simplicity of a saturated network model by not explicitly representing idle states, and yet allows the study of unsaturated nodes. Laufer and Kleinrock [START_REF] Laufer | The capacity of wireless CSMA/CA networks[END_REF] determine the throughput of a node in a CSMA/CA network using the ratio between the transmitting and the backoff periods of that node, its probability of successful transmission, and the channel capacity. The result is then used in the analysis of a network's capacity region, based on nodes' throughputs, under stability conditions. Bonald and Feuillet [START_REF] Bonald | Performance of CSMA in multi-channel wireless networks[END_REF] also characterize both the capacity region and the stability of a wireless network. However, their work focuses on multi-channel networks in either ad-hoc or infrastructure mode, and they propose a refinement to CSMA to achieve a more efficient and fair access to the channel in the infrastructure mode.

In this paper, we study unsaturated, not fully-connected, single-hop IEEE 802.11 wireless networks. We present a conflict graph-based modeling approach to discover the attainable throughput of each node. Our model consists of a single Markov chain which aims at describing, at a high-level of abstraction, the current state of the entire wireless network. Unlike most existing works, our approach is conceptually and computationally simple, enabling it to easily cope with medium sized networks.

III. SYSTEM DESCRIPTION

The considered system is a wireless network using the IEEE 802.11 DCF to access the radio channel. Nodes may represent APs (Access Points), or user stations in infrastructure or adhoc modes. Either way, we study all nodes that belong to the same radio channel. A node detects, but does not necessarily successfully receive, data sent by nodes within its detection range. Throughout this paper, we refer to two nodes that belong to each other's detection ranges as neighbors. For the sake of simplicity, we assume that all nodes are sending their packets at the same speed (i.e., transmission rate).

The network under study consists of N nodes. We use a conflict graph to describe the interactions between the nodes. It is a simple graph of N vertices in which an edge exists between two vertices whenever, in the wireless network, the corresponding nodes belong to each other's detection ranges. Therefore, each pair of neighbor nodes in the network is connected by an edge in the conflict graph. Because we consider that all nodes have the same detection range, the edges in the conflict graph are undirected. Figure. 1 illustrates a simple example of a conflict graph for a four-node network.

Additionally, each node i, (i = 1, . . . , N ), of the network is characterized by its input rate, denoted by x i . The input rate refers to the node's demanded throughput, normalized by the link speed so that possible values for x i range from 0 to 1. We assume that all x i are mutually independent. Note that x i can be regarded as the percentage of time node i demands access to the channel. Because a saturated node always has a packet waiting to be sent, its input rate is equal to 1. As for the performance parameters of a wireless network, customary metrics include the end-to-end delay, the collision and loss rates, the resource utilization, and the attainable throughput. In this paper, we study the normalized attainable throughput (normalized by the link speed) of each node, which we refer to as its output rate. We let y i denote the output rate of node i. In other words, y i expresses the percentage of time in which node i is occupying the channel, i.e., is sending over the channel. It follows that, for i = 1, . . . , N , y i ≤ x i . The second performance parameter we are interested in is the network utilization, denoted by U and calculated as:

U = N i=1 y i U max , (1)
where U max is the maximum network utilization. Otherwise stated, U max is simply the maximum number of nodes that can be simultaneously sending, a quantity that clearly depends only on the conflict graph. Table I summarizes the notation needed to describe the studied system, along with those pertaining to its corresponding model, presented in the next section.

IV. MODELING AND ALGORITHM A. Modeling approach

We now describe our high-level approach to modeling a wireless network as presented in the former section. To cope with the well-known complexity of CSMA/CA-based networks (e.g., random backoff, hidden node problem, starvation), we rely on a single Markov chain, but we deal with two intertwined state spaces, each describing differently and approximately the current state of the network. For the purpose of readability, we illustrate each step of our approach with an example, whose conflict graph is depicted in Fig. 1.

Our foremost state space, denoted by S and referred to as the sending state space, describes which nodes among the N are currently sending, and hence occupying the channel. We denote each sending state of S by S k so that: S = {S k } k≥1 . Therefore, each sending state S k is a vector of size N in which the i-th value, S k (i), is set to 1 if node i is currently sending, and to 0 otherwise. Note that, in our work, a node's sending period includes the data packet transmission itself, as well as all protocol overhead (SIFS and DIFS intervals and ACK transmission). Our objective is to derive a Markov chain representing the possible transitions between these sending states, to compute the probabilities of its state transitions, i.e., its transition matrix, and finally, to derive the steady-state probabilities of S k .

Because we deal with an unsaturated network, we need to introduce a secondary state space, referred to as the activity state space and denoted by A, that describes the activity of each node as being either ON or OFF. A node whose activity is ON has at least one packet waiting to be sent, while an OFF node has currently no backlogged packets. Analogously to S, each activity state, A t k , is a vector of size N whose i-th value denotes the activity of node i. Let P A u l denote the (steadystate) probability that the activity state A u l occurs. The mutual independence of the nodes' input rates x i enables us to obtain P A u l as follows:

P A u l = A u l (i)=ON x i A u l (j)=OFF (1 -x j ). (2)
Note that a sending state, S k , can typically be associated to one or up to T different activity states, each denoted by A t k with t = 1, . . . , T . Indeed, whereas a sending node necessarily implies that its activity is ON, the inverse does not hold. A node that is not sending and has no sending neighbors is (undoubtedly) OFF. On the other hand, if it does have a sending neighbor, then its activity can be either ON or OFF. This means that, when a node is not currently sending, it can be simply because it does not have a packet to be sent, or because it is waiting to access the channel. For example, assuming a given sending state S k = [ 0 1 0 1 ] for our network of four nodes, a total of four activity states (T = 4) may be associated:

A 1 k = [ OFF ON OFF ON ] A 2 k = [ ON ON OFF ON ] A 3 k = [ OFF ON ON ON ] A 4 k = [ ON ON ON ON ] (3)
1) Determining Sending States: An intrinsic property of 802.11-based networks is that two neighbor nodes cannot (or virtually not) be transmitting simultaneously. In terms of modeling, this means that a sending state of the network is possible if and only if it does not include two transmitting vertices connected by an edge in the conflict graph.

In the case of our sample network represented in Fig. 1, out of a total of 16 sending states, only the following seven remain possible for the purpose of our modeling approach:

S 1 = [ 1 0 0 1 ] S 5 = [ 0 1 0 0 ] S 2 = [ 0 1 0 1 ] S 6 = [ 0 0 0 1 ] S 3 = [ 0 0 1 0 ] S 7 = [ 0 0 0 0 ] S 4 = [ 1 0 0 0 ] (4)
2) Establishing Possible Transitions: Having defined the set of possible sending states, S k , we need to decide when we allow a transition from a possible sending state, S k , to another, S l . This transition represents the fact that the network goes from state S k to S l upon a packet-sending completion. We apply a three-rule policy to determine if the transition from S k to S l is possible.

First, at most one element of S k changes its value from 1 to 0 in S l . This rule expresses that no more than one node stops sending at the same time (i.e., upon a change of state in the Markov chain). Considering our sample network, positive examples include transitions from S 1 to S 2 and from S 1 to S 4 . Conversely, a negative example is the transition from S 1 to S 3 .

Second, at most one element of S k changes its value from 0 to 1 in S l , unless in the exception case of a synchronizing node. A node i is said to be synchronizing if (i) it was sending in state S k (i.e., S k (i) = 1), and (ii) it has at least two neighbors that have an ON activity but are not neighbors themselves. The exception allows to account for the situation where a central node's end of sending triggers the beginnings of sending of several of its neighbor nodes. Said differently, in a case with two nodes, labeled m and n, and assuming that they have a common neighbor node i for which S k (i) = 1 and S l (i) = 0, we allow the transition from S k to S l even if we have

S k (m) = S k (n) = 0 and S l (m) = S l (n) = 1.
Apart from this exception, this second rule implies that no more than one node starts sending at the same time. In the case of our sample network, a positive example is the transition from S 4 to S 1 while a negative example is the transition from S 5 to S 1 . The exception to the rule applies twice, namely when we allow the transitions from S 3 to S 1 and from S 3 to S 2 .

Third, considering all potential activity states {A t k } (t = 1, . . . , T ) associated to S k and all potential activity states {A u l } (u = 1, . . . , U ) associated to S l , there must be a combination (A t k , A u l ) in which at most one element changes its value from ON in A t k to OFF in A u l or from OFF to ON. A clear negative example is the transition from S 5 to S 6 (and vice versa) since this would require two nodes, i.e., the second and the fourth, to undergo a simultaneous change of activity.

Overall, the rationale behind these three rules resorts to the fact that we consider as negligible the probability that two nodes undergo simultaneous changes in their behavior (either in terms of sending or activity).

By applying this three-rule policy, we discover all the possible transitions between the sending states, i.e., the transition matrix, in which a value of 1 in the k-th row and l-th column indicates that the transition from S k to S l is possible, and has a value of 0 otherwise. We represent below an extract from the 7 × 7 transition matrix obtained when applying the three-rule policy on the sample four-node network:

S 1 S 2 S 3 S 4 S 5 S 6 S 7           S 1 1
3) Computing Transition Probabilities: The next stage of our modeling approach is to find the probabilities of each transition. Let us consider the transition from S k to S l . First, we evaluate the number of activity states associated to S l that are compatible with S k . An activity state A u l is said to be compatible with S k if there is at least one activity state associated to S k that differs by at most one ON to OFF change (or vice versa) with A u l . We denote by A kl the set of activity states associated to S l that are compatible with S k . For example, in our sample network, there are four activity states associated to S 1 , namely:

A 1 1 = [ ON OFF OFF ON ] A 2 1 = [ ON ON OFF ON ] A 3 1 = [ ON OFF ON ON ] A 4 1 = [ ON ON ON ON ] (6)
while those associated to S 2 are:

A 1 2 = [ OFF ON OFF ON ] A 2 2 = [ ON ON OFF ON ] A 3 2 = [ OFF ON ON ON ] A 4 2 = [ ON ON ON ON ] (7)
We observe that all the activity states associated to S 2 are compatible with S 1 , and thus belong to the set A 12 , i.e., A 12 = {A 1 2 , A 2 2 , A 3 2 , A 4 2 }. Then, we simply derive the transition probability from S k to S l as:

P kl = A u l ∈A kl (P A u l S l (n)=1 1 1 + m∈vn 1 ON(m) ), (8)
where v n represents the set of neighbor nodes of node n. The sum m∈vn 1 ON(m) returns an integer value equal to the number of neighbors of node n that are ON in the activity state A u l . Note that Eq. ( 8) captures that the transition probabilities depend both on the nodes' input rates and the conflict graph. For each activity state A u l that is compatible with the transition from the sending state S k to S l , we calculate the associated transition probability by first assuming that all concerned nodes are evenly likely to access the channel access, and then, we weigh the obtained value by the probability of occurrence of that activity state, P A u l . The term P A u l in Eq. ( 8) ensures that the presence of a node with a high input rate will increase the probability that the whole network is in a sending state in which that node is sending. On the other hand, the other term within the sum represents the fact that a node that is well connected in the conflict graph experiences a lot of competition for channel access, which in turn diminishes its probability of gaining that access.

We now present two refinements to Eq. ( 8) that may occur, or not, depending on the network topology. Considering a given sending state S k , some nodes may be viewed as blocked or as preempted by their neighbors. To cope with these nodes, we simply identify them and remove them from the considered neighbors of node n, i.e., v(n), when using Eq. [START_REF] Nardelli | Closed-form throughput expressions for CSMA networks with collisions and hidden terminals[END_REF]. A node is said to be blocked when it cannot start sending because it has two (or more) sending neighbors. For instance, node 3 is an example of a blocked node when our sample network is in sending state S 1 = [ 1 0 0 1 ]. Indeed, it is very unlikely for node 3 to start sending, as this would require nodes 1 and 4 to simultaneously stop sending. Analogously, a node is said to be preempted if it has one neighbor that is sending, and at least one other neighbor that is ON, which itself has no sending neighbors. This pertains to node 3 when our sample network is in sending state S 4 = [ 1 0 0 0 ] with an activity state [ ON OFF ON ON ]. Under these circumstances, node 4 does not need to wait for the end of node 1's sending in order to start sending, which in turn means node 3 is likely to be preempted. In our modeling approach, we simply account for these nodes by phasing them out from the actual neighborhood of node n when considering the sending state S k . In other words, in Eq. ( 8), we replace the set of neighbor nodes of n, i.e., v(n), by the restricted set of neighbor nodes which excludes blocked and preempted nodes.

The other refinement refers to the case when the z-th node of S k is a synchronizing node (whose definition was stated in Section IV.A.2) and continues to have an ON activity in the next activity state A u l associated to S l . First, for each activity state associated to S l , i.e., A u l , we estimate the probability that the synchronizing node continues to send in S l using:

P z u l = 1 1 + m∈vz 1 ON(m) , (9)
where the sum 1 ON(m) returns an integer value equal to the number of neighbors of node z that are ON in activity state A u l . For example, considering the sending state S 3 of our sample network, node 3 is a synchronizing node. A possible activity state associated to S 3 is [ON OFF ON ON] in which node 3 has two neighbors that are also ON (i.e., nodes 1 and 4). Using Eq. ( 9), we obtain: P z u l = 1 3 . The second step consists in refining the computation of the transition probability P kl as follows:

P kl = A u l ∈A kl (P A u l S l (n)=1 1 1 + m∈wn 1 ON(m) (1-1 z sync .P z u l )), (10
) where 1 z sync .P z u l returns the probability P z u l if a synchronizing node z exists in node n's neighborhood, and 0 otherwise, and w n denotes the restricted neighborhood of node n (without blocked, preempted, and synchronizing nodes).

Finally, we ensure that the matrix is row-stochastic by dividing each P kl probability with the corresponding sum N m=1 P km . 4) Deriving the Output Rates: Having evaluated all the transition probabilities between the sending states, we can easily obtain the steady-state probability of each sending state S k . Let us denote by the vector π = [π S1 , π S2 , ...] the corresponding steady-state probabilities. We then evaluate the output rate of node i by summing the steady-state probabilities π S k over the set of sending state S k in which node i is sending. Hence, we have:

y i = k; S k (i)=1 π S k . (11)
In our sample network, we notice that node 1's is sending only in sending states S 1 and S 4 . Thus, its output rate is given by:

y 1 = π S1 + π S4 .
We conclude by briefly discussing the main approximations involved in our modeling approach. First, in our model, we do not allow two neighbor nodes to simultaneously access the channel. This implies that we neglect the potential collisions, and a fortiori their effect on the network performance. Second, our approach relies on a homogeneous Markov chain in which the transition probabilities are kept constant. In a real CSMA/CA network, owing to the backoff mechanisms, nodes do not have constant odds to access the channel. However, despite these simplifying approximations, our approach provides accurate results as discussed in the next section. Find all the activity states associated to S k as described in Section IV-A 11: end for 12: Blocked nodes: 13: For any node i in a network state S k where S k (i) = 0:

B. Algorithm

14: if ∃m, n ∈ {v i } 2 s.t. S k (m) = S k (n) = 1 then 15:
node i is a blocked node in state S k 16: end if 17: Preempted nodes: 18: For any node i in a network state S k and its activity state Calculate activity state probabilities using [START_REF] Cali | IEEE 802.11 wireless LAN: capacity analysis and protocol enhancement[END_REF] 42:

A t k where S k (i) = 0: 19: if ∃m, n ∈ {v i } 2 , m / ∈ v n s.t. S k (m) = 1 and A t k (n) = ON and ∃r ∈ v n s.t. S k (r) =
: if ∃m, n ∈ {v i } 2 , m / ∈ v n s.t. A t k (m) = A t k (n) = ON then
If synchronizing nodes exist, calculate P z u l using [START_REF] Durvy | Self-organization properties of CSMA/CA systems and their consequences on fairness[END_REF] 43:

Calculate the probability P kl of T kl with (10) 44: end for 45: Normalize:

Normalize each transition probability P kl by diving it with the sum of all transition probabilities of transitions leaving state S k . 46: Solve the chain: Find the stationary distribution π of the Markov chain created by the states in S and the transitions in T 47: Calculate output rates: Use [START_REF] Boorstyn | Throughput analysis in multihop csma packet radio networks[END_REF] to calculate the output rates of all N nodes.

V. NUMERICAL RESULTS

We begin this section with a study of our model's accuracy in predicting output rates. Then, we present two examples of possible applications. Throughout this section, all results were obtained using the IEEE 802.11g standard with a link speed of 54 Mbps. All nodes have equal detection ranges and transmit packets with a fixed size of 500 bytes.

A. Accuracy validation

We evaluate the accuracy of our model by comparing its values with those provided by the discrete-event simulator ns2 [START_REF]The Network Simulator[END_REF]. Every simulation point presented in the results is the average of 20 independent simulation runs lasting 60 seconds each. The resulting confidence intervals are very narrow so we only use the mid-point in our validation. As for the input rates x i , we represent their intensity in the simulator by alternating between active and inactive periods with exponentially distributed lengths whose mean values ratio is set to x i . In active periods the node's queue is constantly backlogged, while in inactive period its queue is empty and the node is not attempting to access the channel. The throughput obtained in simulation is then normalized by the link speed, in order to obtain the dimensionless output rate, y i , which is comparable with that of our model.

In our first example, we consider the four-node network of Fig. 1. We set the input rates of nodes 1, 3, and 4 to x 1 = 0.5, x 3 = 1, x 4 = 0.5, respectively. On the other hand, we let the input rate of node 2 vary from x 2 = 0 (always off) to x 2 = 1 (constant saturation), taking several values in that interval. We then evaluate the output rates of nodes 1 and 2, i.e., y 1 and y 2 , as well as the network utilization, as delivered by the simulator and by our model. Figure . 2 shows the corresponding results.

As expected, as the input rate of node 2, i.e., x 2 , grows from 0 to 1, so does its output rate, i.e., y 2 , though to a lesser extent. Because y 2 < x 2 (except for x 2 = 0), we conclude that node 2 cannot meet all its demands, regardless of their actual intensity. As for node 1, whose input rate x 1 is kept constant, its output rate tends to decrease with increasing values of x 2 . This behavior ensues from the competition between nodes 1 and 2. Note that, even for x 2 = 0, node 1 struggles to meet its demands as y 1 = 0.4 (while x 1 = 0.5). Finally, the network utilization grows steadily from around 0.6 to 0.75 as the input rate of node 2 increases. Overall, we observe that our proposed model is able to accurately capture these behaviors with a relative error typically less than 10%.

The second example involves a more complex network with a nine-node topology whose conflict graph is given in Fig. 3. Here, we consider several values for the input rate for node 6, x 6 , ranging from 0 to 1 while we keep the input rates of other nodes constant, i.e., x 1 = 0.7, x 2 = 0.8, x 3 = 0.6, x 4 = 0.5, x 5 = 0.8, x 7 = 0.7, x 8 = 0.6, and x 9 = 0.9.

The corresponding results are shown in Fig. 4. In order to keep the figure legible, we choose to trace the output rates of nodes 5, 6, 7, and 9, bearing in mind that node 8's output rate evolves similarly to that of node 7, and that the first four nodes of the network are not highly influenced by the change in input rate of node 6. We observe that, as x 6 grows from 0 to 1, the behaviors of nodes can be significantly changed, with some increasing their output rates (e.g., nodes 6 and 9), while others experience a decrease (e.g., nodes 5 and 7), that may result in a near node starvation as x 6 comes closer to 1. As shown by Fig. 4, our model was able to reproduce these non-trivial behaviors with a good degree of precision. In the aim of providing a more comprehensive idea of the accuracy of our model, we present, in Table II, the overall error distribution obtained on over 250 samples. Each sample depicts the precision of the output rate of a node in the nine or four-node network. The median value indicates that, in 50% of the samples, the deviation between y i as returned by the simulator and by our model is less than 0.047. Table II also shows that, in all our samples, the difference between the model's and the simulator's y i is never larger than 0.20. Note that in order to investigate the robustness of our approach, we explored several other examples with different network topologies, packet sizes, and means and distributions for the active and inactive periods. Due to space constraints, the corresponding results are not presented in this paper. However, it was our experience that our model's accuracy was similar to that described by the two former examples.

Median

B. Model applications

Having validated the accuracy of our model, we now describe how its application can help to improve the general behavior of a network by ensuring a better share of the channel resources. In the two scenarios that follow, we assume the nodes to be APs. Furthermore, we assume the presence of a network controller possessing the knowledge of the nodes' input rates and the network topology. We show how such a controller can be used to either restrain a node's input rate, or to completely turn off a node, in the goal of improving the network's performance.

In our first scenario, we suppose that the controller is able to regulate the input rate of a given node. Let us consider the nine-node network of Fig. 3 and that node 9 is selected. Note that node 9 plays a central role in the network topology as it is able to block or preempt nodes 7 and 8 with the help of node 6. Using our model, we discover the output rates of all nodes (including y 9 ) for values of x 9 ranging from 0.2 to 1, and we compute the associated value of Jain's index [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF], a commonly used metric of fairness revealing how close the y i values are to each other. Figure 5 reports the corresponding results. As expected, we observe that, as we relax the constraint on x 9 , nodes 7 and 8 undergo a significant decrease in their output rates, unlike node 6 that experiences a growth of its output rate. More interestingly, the network's Jain's index exhibits a peak value for x 9 close to 0.35. This peak is about 30% higher than the value obtained with x 9 = 1. In other words, to ensure a fair share of the channel resources among the nodes, the best scheme would be to restrain the input rate of node 9 to no more than x 9 = 0.35.

Our second scenario addresses the case in which the network controller is entitled to completely turn off a node (e.g., by moving it to another radio channel). Our goal is to show how our model can help determine which node should be turned off in order to maximize a given performance metric (Jain's index or the network utilization U ). To that effect, we consider the ten-node network whose conflict graph is given in Fig. 6 in which the input rates have been set to x 1 = 0.3, x 2 = 0.6, x 3 = 0.8, x 4 = 0.5, x 5 = 0.7, x 6 = 0.3, x 7 = 0. x 8 = 0.4, x 9 = 0.9, and x 10 = 0.7. One at a time, we turn off each node of the network, and then we calculate the nodes' output rates, together with the Jain's index and the network utilization. The corresponding results are shown in Fig. 7. Note that Ni denotes the case where the i-th node is turned off, while Original refers to the original ten-node network without any nodes off. It appears that turning node 3 off would be the best option as not only does it allow to achieve the largest network utilization, but also maximizes the Jain's fairness index. 6 VI. CONCLUSIONS In this paper, we consider the performance evaluation of unsaturated, and not fully-connected networks based on IEEE 802.11 DCF. We present a conflict graph-based modeling approach to discover the attainable throughput of each node. Our model consists of a single Markov chain which aims at describing, at a high-level of abstraction, the current state of the entire wireless network. Owing to its low complexity, our approach is simple to implement, can cope with medium sized networks, and its execution speed is fast. We validate its accuracy against a discrete-event simulator. Results show that our approach is typically accurate, with associated relative errors generally less than 15%, and that it captures complex phenomena such as node starvation. We investigate two potential applications of our proposed approach in which, starting with a given network, we improve its performance in terms of overall throughput or fairness by throttling the throughput demand of a node, or by turning a node off altogether. Future works aim at validating our model against real-life measurements.

Fig. 1 :

 1 Fig. 1: Conflict graph for a four-node network.

Algorithm 1 1 : 8 :

 18 Sending States: Find all possible sending states: 2: S = {0, 1} N 3: for k = |S| ...1 do 4: if S k contains two sending neighbor nodes then 5: remove S k from S 6: end if 7: end for Activity States: 9: for S k ∈ S do 10:

  a synchronizing node for nodes m and n 26: end if 27: Transitions: Find the possible network state transitions 28: for k = 1... |S| ; l = 1... |S| do 29: if S k → S l implies more than one 1 → 0 change in the network state then 30: transition T kl is not possible 31: else if S k → S l implies more than one 0 → 1 change in the network state except for having up to n such changes in the n nodes synchronized by the same node then 32: transition T kl is not possible 33: else if there is no state A u l compatible with S k then 34: transition T kl is not possible 35: for 39: Probabilities: Calculate all transition probabilities 40: for T kl ∈ T do 41:

Fig. 2 :

 2 Fig. 2: Accuracy for the network of Fig. 1 as a function of node 2's input rate.

Fig. 3 :Fig. 4 :

 34 Fig. 3: Conflict graph for a nine-node network.

Fig. 5 :

 5 Fig. 5: Jain's fairness index and output rates for the network of Fig. 3 as a function of node 9's input rate.

Fig. 6 :

 6 Fig. 6: Conflict graph for a ten-node network.

Fig. 7 :

 7 Fig. 7: Jain's fairness index and network utilization for the network in Fig. 6

  N total number of nodes v i the set of neighbors of node i, v i ⊆ {1, 2, ..., N } w i the restricted set of neighbors of node i with synchronized, blocked, and preempted nodes removed S the set of possible sending states, S ⊆ {0, 1} N S k k-th sending state, S k ∈ S S k (i) state of node i in sending state S k , S k (i) ∈ {0, 1}, where 1 means node i is sending A the set of possible activity states, A = {ON, OFF} N

	A t k A kl	an activity state associated to sending state S k , A t k ∈ A the set of all activity states associated to sending state S l and
	P A t k T	compatible with sending state S k probability of occurrence of activity state A t k the set of possible transitions between sending states
	T kl	transition from sending state S k to S l , T kl ∈ T
	P kl	probability of transition from sending state S k to state S l
	x i	input rate of i-th node, x i ∈ [0, 1]
	y i	output rate of i-th node, y i ∈ [0, 1]
	U	network utilization, U ∈ [0, 1]
	π	stationary probability distribution of the Markov chain that
		describes the network
	π S k	steady state probability of sending state S k

TABLE I :

 I Notation.

  1 then Synchronized nodes: 23: For any node i in a network state S k where S k (i) = 1 and an activity state A t k : 24

	20:	node i is a preempted node in state S k for activity
		state A t k
	21: end if
	22:

TABLE II :

 II Distribution of the absolute errors for the output rates, y i .

  5,

		0.9
		0.8
	i , and Jain's index Output rates, y	0.2 0.3 0.4 0.5 0.6 0.7							Node 5 Node 6 Node 7 Node 8 Node 9 Jain's index
		0.1
		0
		0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
					Input rate of node 9, x 9