318
`
`IEEE COMMUNICATIONS LETTERS, VOL. 2, NO. 12, DECEMBER 1998
`
`IEEE 802.11—Saturation Throughput Analysis
`
`Giuseppe Bianchi
`
`Abstract—To satisfy the emerging need of wireless data commu-
`nications, IEEE is currently standardizing the 802.11 protocol for
`wireless local area networks. This standard adopts a CSMA/CA
`medium access control protocol with exponential backoff. In
`this letter, we present a simple analytical model to compute the
`saturation throughput performance in the presence of a finite
`number of terminals and in the assumption of ideal channel
`conditions. The model applies to both basic and RTS/CTS access
`mechanisms. Comparison with simulation results shows that the
`model is extremely accurate in predicting the system throughput.
`
`Index Terms— IEEE 802.11 protocol, multiple access control,
`performance evaluation.
`
`Fig. 1. Basic access mechanism.
`
`TO ACCESS the medium,
`
`I. INTRODUCTION
`IEEE 802.11 employs a
`CSMA/CA (carrier sense multiple access with collision
`avoidance) MAC protocol with binary exponential backoff,
`called distributed coordination function (DCF)
`[1]. DCF
`defines a basic access method, and an optional four-way
`handshaking technique, known as request-to-send/clear-to-
`send (RTS/CTS) method.
`This letter provides a simple but nevertheless very accurate
`analysis to compute the throughput of both basic and RTS/CTS
`access schemes, in the assumption of ideal channel (see [2] and
`[3] for approximate models that account for hidden terminals
`and capture). We focus on the saturation throughput, which is
`a fundamental performance figure defined as the limit reached
`by the system throughput as the offered load increases, and
`it represents the maximum load that the system can carry
`in stable conditions (as in most random access protocols, the
`maximum throughput may be greater than the saturation one,
`but it is of no practical importance as not sustainable for “long”
`time—see a general discussion about stability in [4]).
`
`II. DISTRIBUTED COORDINATION FUNCTION
`The DCF basic access method [1] is shortly summarized
`as follows. A station with a packet to transmit, monitors the
`channel activity until an idle period equal to a distributed
`interframe space (DIFS) is detected. The time immediately
`following an idle DIFS is slotted, and a station is allowed to
`transmit only at the beginning of each slot time, defined as
`the time needed at any station to detect the transmission of a
`packet from any other station. It accounts for the propagation
`delay, for the time needed to switch from the receiving to
`
`Manuscript received February 9, 1998. The associate editor coordinating
`the review of this letter and approving it for publication was Dr. K. Sriram.
`The author is with the Dipartimento di Elettronica e Informazione, Politec-
`nico di Milano, 20133 Milano, Italy (e-mail: bianchi@elet.polimi.it).
`Publisher Item Identifier S 1089-7798(98)09502-7.
`
`the transmitting state (RX TX Turnaround Time), and for the
`time to signal to the MAC layer the state of the channel (busy
`detect time).
`After sensing an idle DIFS, the station generates a random
`backoff interval before transmitting. The backoff time counter
`is decremented as long as the channel is sensed idle, stopped
`when a transmission is detected on the channel, and reactivated
`when the channel
`is sensed idle again for more than a
`DIFS (see Fig. 1). The station transmits when the backoff
`time reaches zero. At each transmission, the backoff time
`is uniformly chosen in the range
`. At the first
`transmission attempt,
`, namely the minimum backoff
`window. After each unsuccessful transmission,
`is doubled,
`up to a maximum value
`.
`Since the CSMA/CA does not rely on the capability of the
`stations to detect a collision by hearing their own transmission,
`a positive acknowledgment (ACK) is transmitted by the des-
`tination station to signal the successful packet transmission.
`To allow an immediate response,
`the ACK is transmitted
`following the received packet, after a short interframe space
`(SIFS). If the transmitting station does not receive the ACK
`within a specified ACK Timeout, or it detects the transmission
`of a different packet on the channel, it reschedules the packet
`transmission according to the previous backoff rules.
`The standard defines an additional mechanism of four-
`way handshaking to be optionally used in the case a packet
`exceeds a specified length, to improve the system throughput
`by shortening the duration of the collisions. This mechanism
`requires the transmission of special short request to send (RTS)
`and clear to send (CTS) frames prior to the transmission of
`the actual data frame. As shown in Fig. 2, an RTS frame is
`transmitted by a station which needs to transmit a packet.
`When the receiving station detects an RTS frame, it responds,
`after a SIFS, with a CTS frame. The transmitting station is
`thus allowed to transmit its packet only if it correctly receives
`the CTS frame. Moreover, the frames RTS and CTS carry
`1089–7798/98$10.00 ª
`
`1998 IEEE
`
`Ex. 1012 / Page 1 of 3
`ERICSSON v. UNILOC
`
`

`

`BIANCHI: IEEE 802.11—SATURATION THROUGHPUT ANALYSIS
`
`319
`
`Fig. 2. RTS/CTS access mechanism.
`
`the information of the length of the packet to be transmitted.
`This information can be read by each station, which is then
`able to update a network allocation vector (NAV) containing
`the information of the period of time in which the channel
`will remain busy. This latter technique has been introduced to
`combat the system degradation due to hidden terminals [5]. In
`fact, a station able to detect the transmission of at least one of
`the RTS or CTS frames, can avoid collision even when unable
`to sense the channel busy.
`
`III. THROUGHPUT ANALYSIS
`Consider a fixed number
`of contending stations. In satu-
`ration conditions, each station has immediately a packet avail-
`able for transmission, after the completion of each successful
`transmission. Let
`be the stochastic process representing
`the size of the backoff window for a given station at slot
`time
`(note that, as shown in Fig. 1, the time is stopped
`when the channel is sensed busy). Clearly, this process is
`non-Markovian. However, define for convenience
`,
`where
`is called “backoff stage,” and let
`be the
`stochastic process representing the backoff stage
`of the station at time .
`The key approximation in our model is that the probability
`that a transmitted packet collides is independent on the state
`of the station (this is more accurate as
`and
`are larger).
`In this condition, the bidimensional process
`is
`a discrete-time Markov chain, for convenience depicted in
`Fig. 3, with the only nonnull one-step transition probabilities
`being1
`
`Fig. 3. Markov chain model for the backoff window size.
`
`Owing to the chain regularities, the following relations hold:
`
`The value of
`condition
`
`is determined by imposing the normalization
`
`from which
`
`Let
`be the probability that a station transmits in a
`generic slot time. As any transmission occurs when the backoff
`window is equal to zero, regardless of the backoff stage, it is
`
`(1)
`
`These transition probabilities account, respectively, for: 1) the
`decrement of the backoff time counter; 2) the fact that a
`new packet following a successful transmission starts with
`a backoff stage 0; and 3), 4) the fact that after an unsuc-
`cessful transmission at backoff stage , the backoff interval is
`uniformly chosen in the range
`.
`Let
`
`,
`,
`be the stationary distribution of the chain.
`
`1 We adopt the short notation: P fi1; k1ji0; k0g = P fs(t + 1) = i1,
`b(t + 1) = k1js(t) = i0; b(t) = k0g.
`
`(2)
`
`To finally compute the probability
`that a transmitted
`packet collides, note that
`is the probability that, in a time
`slot, at least one of the
`remaining stations transmits
`
`(3)
`
`where
`is given in (2) as function of the only unknown .
`Numerically solving (3), the value of
`, and therefore, of
`,
`is found. Once
`is known, the probability
`that in a slot
`time there is at least one transmission, given
`active stations,
`
`Ex. 1012 / Page 2 of 3
`ERICSSON v. UNILOC
`
`

`

`320
`
`and the probability
`readily obtained as
`
`that a transmission is successful, are
`
`(4)
`
`(5)
`
`the r.v. representing the number of consecutive idle
`Being
`slots between two consecutive transmissions on the channel
`(see Fig. 1), it is
`
`(6)
`
`We are finally in the condition to determine the normalized
`system throughput
`, defined as the fraction of time the
`channel is used to successfully transmit payload bits. As the
`instants of time right after the end of a transmission are
`renewal points, it is sufficient to analyze a single renewal
`interval between two consecutive transmissions, and express
`as the ratio
`timeused for successful transm. in interval
`length of a renewal interval
`
`(7)
`
`is the average
`is the average packet length,
`where
`time the channel
`is sensed busy because of a successful
`transmission, and
`is the average time the channel is sensed
`busy by the stations during a collision. The times
`,
`and
`must be measured in slot times, as this is the time unit
`of
`.
`To conclude the analysis, it remains only to specify the
`values
`and
`. Let
`be the packet
`header, and
`be the propagation delay. For the basic access
`method it is (see Fig. 1):
`
`is the average length of the longest packet
`where
`payload involved in a collision2: in the case all packets have
`the same fixed size,
`.
`is the time in
`which the channel is sensed busy by the noncolliding stations:
`we have neglected the fact that the two or more colliding
`stations, before sensing the channel again, need to wait an
`additional SIFS plus an ACK timeout (the same approximation
`holds in the following RTS/CTS case, with a CTS timeout
`instead of the ACK timeout).
`For the RTS/CTS access method, assuming for simplicity of
`presentation that all the stations use the RTS/CTS mechanism
`for all
`the transmitted packets, regardless of the packet’s
`length, it is (see Fig. 2)
`
`2 When the probability of three of more packets simultaneously colliding is
`neglected, this is given by E[ max (P1; P2)], where Pi are independent and
`identically distributed r.v.s. To proceed further it is then necessary to assume
`a suitable pdf for the packet’s length.
`
`IEEE COMMUNICATIONS LETTERS, VOL. 2, NO. 12, DECEMBER 1998
`
`Fig. 4. Saturation throughput: Analysis versus simulation.
`
`IV. MODEL VALIDATION
`To validate the model, we have compared its results with
`that obtained with the 802.11 DCF simulator used in [6],
`which accounts for all the protocol details. The packet payload
`length has been chosen constant and equal
`to 8184 bits.
`The other protocol and channel parameters adopted are those
`specified for the FH (frequency hopping) PHY layer [1], and
`are reported in the following table (additional parameters are
`specified in [6]):
`
`packet payload
`MAC header
`PHY header
`ACK length
`RTS length
`CTS length
`Channel Bit Rate
`Propagation Delay
`SIFS
`Slot Time
`DIFS
`
`8184 bits
`272 bits
`128 bits
`112 bits + PHY header
`160 bits + PHY header
`112 bits + PHY header
`1 Mbit/s
`1 s
`28 s
`50 s
`128 s
`
`Fig. 4 shows that the analytical model is highly accurate: an-
`alytical results (lines) practically coincide with the simulation
`results (simbols), in both basic access and RTS/CTS cases. All
`simulation results are obtained with a 95% confidence interval
`lower than 0.002.
`
`REFERENCES
`
`[1] P802.11, “IEEE standard for wireless LAN medium access control
`(MAC) and physical layer (PHY) specifications,” Nov. 1997.
`[2] H. S. Chhaya and S. Gupta, “Performance modeling of asynchronous
`data transfer methods of IEEE 802.11 MAC protocol,” Wireless Net-
`works, vol. 3, pp. 217–234, 1997.
`[3] K. C. Huang and K. C. Chen, “Interference analysis of nonpersistent
`CSMA with hidden terminals in multicell wireless data networks,” in
`Proc. IEEE PIMRC’95, Toronto, Ont., Canada, Sept. 1995, pp. 907–911.
`[4] D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs. NJ:
`Prentice Hall, 1987.
`[5] L. Kleinrock and F. Tobagi, “Packet switching in radio channels: Part
`II—The hidden terminal problem in carrier sense multiple access and
`the busy tone solution,” IEEE Trans. Commun., vol. COM-23, pp.
`1417–1433, Dec. 1975.
`[6] G. Bianchi, L. Fratta, and M. Oliveri, “Performance evaluation and
`enhancement of the CSMA/CA MAC protocol for 802.11 wireless
`LAN’s,” in Proc. PIMRC 1996, Taipei, Taiwan, R.O.C., Oct. 1996, pp.
`392–396.
`
`Ex. 1012 / Page 3 of 3
`ERICSSON v. UNILOC
`
`