DOC PREVIEW
Berkeley ELENG 228A - Lecture Notes

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1EE228a - Lecture 5 - Spring 2006WiFi ModelsScribed by Libin Jiang (ljiang@eecs)AbstractThis lecture describes WiFi models via an example of QoS over IEEE 802.11 network. First we will give an overviewof 802.11 protocol. Then a model proposed by Bianchi [1] will be presented to compute the packet delay of 802.11 DCF(Distributed Coordination Function). We extend this model to 802.11e EDCF (Extended Distributed CoordinationFunction) to study the QoS for voice it can provide.I. Overview of IEEE 802.11Fig. 1IEEE 802.11 Infrastructure NetworkFig 1 shows typical data traffic in an 802.11 Infrastructure network. A number of wireless hosts/clients communicatewith an AP (Access Point), which is normally attached to a wired network (e.g. Ethernet). In 802.11b, except that thephysical header of each packet is transmitted at the same data rate, each station can choose one of the four rates for theMAC layer payload from 11Mbps, 5.5Mbps, 2Mbps and 1Mbps, depending on the wireless channel condition (a lowerrate is chosen for a weaker channel to guarantee the probability of error). There are ”downlink” traffic from the AP,and ”uplink” traffic to the AP. For VoIP (Voice over IP), downlink and uplink traffic are symmetric. In this lecture, wewill focus on deriving the packet delay and providing QoS in such networks.There are two types of functions in 802.11 MAC: Point Coordination Function (PCF) and Distributed CoordinationFunction (DCF). PCF is a polling protocol, which enables the clients to transmit data one by one. This function,however, is not robust, and is not implemented in most products. PCF is simple to analyze because of its similarity toTDMA.The commonly implemented DCF is based on CSMA/CA (Carrier Sensing Multiple Access/Collision Avoidance).Each station (including the AP and clients) randomly chooses a time slot to transmit a packet. If packet is collided(when another station happens to choose the same slot), it will double its Backoff-Window and try again later. DCFis more difficult to analyze due to its random nature. In 802.11b with rate 11Mbps, pure data transmission typicallygets a throughput of 6Mbps; and for VoIP with 64kbps/direction, 12 connections can be supported (about 1.5Mbps intotal). The remaining bandwidth is spent in collisions, backoffs and packet headers. Fig 2 shows how DCF works.II. Analyzing VoIP in 802.11 DCFWe wish to support n VoIP connections (Fig 3). That is, we hope to send V1, V2, ..., Vnin 20 ms. Given a data rateof the network, there is a maximum n feasible, which is the ”Call Capacity”. Note that the bottleneck is at the AP,since AP needs to send n flows. Our approach to find the Call Capacity is shown in Fig 4. After assuming a numberof connections, we derive the delay and check whether the delay requirement is met at the AP. If not, this number isbeyond the Call Capacity.Bianchi’s Model2Fig. 2Distributed Coordination FunctionFig. 3Pure VoIP in an 802.11 networkFig. 4Approach to determine Call CapacitySince Bianchi’s Model [1] is used in the above process (Fig 4), we introduce this model in the following. Bianchi’sModel is a discrete model with variable slot size. There are 3 different slot sizes (See Fig 5):• Idle slot• Success slot TS= V oIP + SIF S + ACK + D IF S• Collision slot TC= V oIP + EIF Swhere V oIP = (RT P + UDP + IP + MAC + payload)/rate.Bianchi used a Markov chain (Fig 6) to model the state transition of each station. The state of the Markov chainis (backoff stage, backoff counter). When a collision occurs, the backoff stage increases, corresponding to moving downthe chain vertically to the next row. The station chooses uniformly the backoff time in [0,Wm-1], Wm states in a row,where Wm= 2mCWminis the maximum back off time for backoff stage m. The counter decrements in each slot untilit reaches 0 and try to transmit again. By solving the steady state probability of the Markov chain, the probability, p1,for station 1 to transmit a packet in a slot, can be expressed in terms of c1, the collision probability of station 1.The next step is to consider the whole network. Rigorously, the Markov chains of different stations are coupled.But for simplification, they are assumed to be independent. (Similar examples: In circuit switching network, eachcall is assumed to be blocked independently by different links. In packet switched network, ”Kleinrock independenceapproximation” can be used in M/M/1 queuing model.) So, c1isc1= 1 − Πi6=1(1 − pi)3Fig. 5Timeline of 802.11 DCFFig. 6Bianchi: 802.11 Markov chain. (This is the Markov chain of station 1. c1is the probability ofcollision when station 1 transmit)Then we obtain a set of equations, as listed in Fig 7. cA, cVare respectively the collision probability of the AP andthe host (Fig 3), NVis the number of VoIP hosts, and dnis the total time needed to transmit a packet (dAfor theAP and dVfor the host). Note that Bianchi’s model assumes that all the stations are ”saturated” (i.e., they alwayshave packets to send). But in our case, this is not true. So in the first two equations (on the right-hand-side) in Fig 7,we need to multiply p(pAorpV) by λ(λAorλV), where λ is the fraction of time when a station is transmitting packets(here is another approximation). It is expressed in equation 3 and 4 (right-hand-side) in Fig 7, where T is the ”cycle”time during which the AP transmit NVpackets and each client transmit one packet. According to the M/G/1 queueingmodel (Fig 8), the waiting time for voice packet isWV= WVq+ WVrFrom Little’s formula, E[WVq] =NVE[WV]TE[dA]. Then, E[WV] = E[WVr]/(1 −NVE[dA]T), where E[WVr] =NVE[dA2]2T. Finally, the average delay at the AP is E[WV] + E[dA] (recall that the AP is the bottleneck).Now we verify the model through ns-2 simulations. In Fig 9, we compare the ”mean packet delay at the AP” derivedfrom the model with that obtained from simulations. The model proves to b e a good approximation.4Fig. 7A set of system equationsFig. 8M/G/1 queue for delay analysisIn 802.11 networks, the throughput can be maximized by (1) limiting the number of contending stations; and/or (2)using large packet payload. These approaches are not suitable for VoIP.II I. 802.11e EDCF’s Support to VoIP802.11e EDCF is designed for differentiated service. In EDCF (Fig 10), voice receives priority over data. This isachieved by• Choosing random backoff from smaller window (e.g, from a Backoff-Window of [0, 3] instead of [0, 15])• Waiting less time


View Full Document

Berkeley ELENG 228A - Lecture Notes

Documents in this Course
FAST TCP

FAST TCP

57 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?