Software

25 pages
3 views

Sticky CSMA/CA: Implicit synchronization and real-time QoS in mesh networks

of 25
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Sticky CSMA/CA: Implicit synchronization and real-time QoS in mesh networks
Transcript
  Sticky CSMA/CA: Implicit synchronization and real-timeQoS in mesh networks Sumit Singh  a,* , Prashanth Aravinda Kumar Acharya  b , Upamanyu Madhow  a ,Elizabeth M. Belding-Royer  b a Department of Electrical and Computer Engineering, University of California, Santa Barbara, CA 93106, United States b Department of Computer Science, University of California, Santa Barbara, CA 93106, United States Received 31 March 2006; received in revised form 24 October 2006; accepted 9 December 2006Available online 14 January 2007 Abstract We propose a novel approach to QoS for real-time traffic over wireless mesh networks, in which application layercharacteristics are exploited or shaped in the design of medium access control. Specifically, we consider the problem of efficiently supporting a mix of Voice over IP (VoIP) and delay-insensitive traffic, assuming a narrowband physical layerwith CSMA/CA capabilities. The VoIP call carrying capacity of wireless mesh networks based on classical CSMA/CA(e.g., the IEEE 802.11 standard) is low compared to the raw available bandwidth, due to lack of bandwidth and delayguarantees. Time Division Multiplexing (TDM) could potentially provide such guarantees, but it requires fine-grained net-work-wide synchronization and scheduling, which are difficult to implement. In this paper, we introduce Sticky CSMA/CA, a new medium access mechanism that provides TDM-like performance to real-time flows without requiring explicitsynchronization. We exploit the natural periodicity of VoIP flows to obtain implicit synchronization and multiplexinggains. Nodes monitor the medium using the standard CSMA/CA mechanism, except that they remember the recent historyof activity in the medium. A newly arriving VoIP flow uses this information to grab the medium at the first availableopportunity, and then  sticks  to a periodic schedule, providing delay and bandwidth guarantees. Delay-insensitive trafficfills the gaps left by the real-time flows using novel contention mechanisms to ensure efficient use of the leftover bandwidth.Large gains over IEEE 802.11 networks are demonstrated in terms of increased voice call carrying capacity (more than100% in some cases). We briefly discuss extensions of these ideas to a broader class of real-time applications, in which arti-ficially imposing periodicity (or some other form of regularity) at the application layer can lead to significant enhancementsof QoS due to improved medium access.   2007 Elsevier B.V. All rights reserved. Keywords:  Mesh networks; Quality of service; Medium access control; Voice over IP; Time division multiplexing 1. Introduction Wireless mesh networks offer an attractive solu-tion for providing voice, multimedia, and best effortdata services in areas where deployment of a wiredinfrastructure is not viable or is economically 1570-8705/$ - see front matter    2007 Elsevier B.V. All rights reserved.doi:10.1016/j.adhoc.2006.12.008 * Corresponding author. Tel.: +1 805 893 7520. E-mail addresses:  sumit@ece.ucsb.edu (S. Singh), acharya@cs.ucsb.edu (P.A.K. Acharya), madhow@ece.ucsb.edu (U. Mad- how), ebelding@cs.ucsb.edu (E.M. Belding-Royer).Ad Hoc Networks 5 (2007) 744–768 www.elsevier.com/locate/adhoc  unattractive. Such networks can extend the reach of the wired backbone through a backhaul mesh of wireless routers, not only providing communicationservices to remote areas but also offering a flexibleand economical means of scaling network capacityto serve increasing demand in enterprises and cam-pus communities. Mesh networks can also providea self-contained communication infrastructure thatcan be deployed in a plug-and-play fashion forsearch, rescue and disaster recovery operations.However, a key drawback of current wireless meshtechnology based on IEEE 802.11 standards is thatit is not possible to provide bandwidth and delayguarantees to real-time applications such as voiceand video [1]. The primary reason is the variabilityin delay and loss performance that results fromthe requirement that each packet must contendafresh for the medium. These drawbacks of IEEE802.11 are only partly alleviated by its QoS exten-sion IEEE 802.11e. Given that medium accesscontrol is the bottleneck for providing QoS, analternative approach is to employ Time DivisionMultiplexing (TDM) to obtain a collision-freetransmission schedule. However, this requires fine-grained network-wide synchronization and schedul-ing, which are difficult to implement. In this paper,we introduce Sticky CSMA/CA, 1 a new mediumaccess control mechanism that provides TDM-likeperformance to real-time flows without requiringexplicit synchronization.Our starting point is the observation that thetraffic generated by real-time flows exhibits a signif-icant regularity. Can this regularity be exploited formore effective medium access control? After all,contention between nodes occurs because a nodecannot predict the actions of its neighbors. If thetransmission schedule for a node follows a regularpattern, its neighbors should be able to learn thispattern using the CSMA mechanism, and thusavoid contention. While these ideas are potentiallyapplicable to a broad class of real-time flows, in thispaper, we focus specifically on illustrating how theyenable efficient support of Voice over IP (VoIP)over wireless mesh networks. The success of VoIPover the wireline Internet leads us to expect that itwill be a key application driving the wider accep-tance and commercial success of wireless mesh net-works. A broad range of wireless VoIP solutions arecommercially available and are being deployed inenterprises and campuses [3,4]. However, theseproducts typically optimize VoIP performance overa single wireless hop from a tetherless node to anAccess Point connected to the wired network. Ourgoal is to support VoIP in wireless mesh networks,thus significantly increasing the flexibility of deploy-ment. The challenge is to provide an adequate levelof QoS, in terms of assured bandwidth, andbounded delay and delay jitter.Sticky CSMA/CA is based on the assumptionthat all the real-time flows in the network are eithernaturally periodic (e.g., VoIP) or have been shapedby the higher layers as periodic (constant bit rate)streams with the same period. A node that has totransmit packets from a real-time flow monitorsthe medium using the standard CSMA mechanism.When it detects an opportunity to transmit, itattempts packet transmission, and on being success-ful,  sticks  to a periodic schedule. Neighbors detectsuch periodic schedules using the CSMA mecha-nism and avoid interfering with them. This mediumaccess approach leads to a TDM-like sharing of themedium among the real-time flows, with the period-icity of the application and transmission schedulebeing used to obtain an implicit form of synchroni-zation. Delay-insensitive traffic has a lower prioritythan real-time traffic and utilizes the bandwidth leftover from the real-time flows.From the point of view of implementation,Sticky CSMA/CA requires that the nodes maintain carrier sense tables  that record the periodic flowswhose existence it can infer using the CSMA mech-anism. Upon arrival of a new real-time flow, a nodelooks at its carrier sense table to determine a peri-odic schedule over which the medium is free, andcontends for and grabs the medium at the first suchopportunity (i.e., it starts sending in a time intervalthat does not interfere with the existing real-timeflows in its carrier sense table). If the flow setup issuccessful, the node locks onto a periodic transmis-sion schedule. All the other nodes in the networkthat overhear the control message exchange updatetheir carrier sense tables immediately, and the nodesthat sense the new periodic transmission infer that anew flow has been set up. Delay-insensitive traffichas lower priority than real-time traffic and fills inthe gaps remaining after the real-time flows havebeen accommodated. We develop new contentionresolution mechanisms for delay-insensitive traffic 1 The term  sticky routing   has been used for routing protocols intelephone networks [2] that grab and hold resources whilefeasible. Sticky CSMA/CA also grabs and holds resources, butfor channel access: the context and protocol details are com-pletely different. S. Singh et al. / Ad Hoc Networks 5 (2007) 744–768  745  that enhance the efficiency with which they utilizethe left-over bandwidth.Our performance evaluations focus on a mix of VoIP and data traffic, for which large gains in VoIPcall carrying capacity are demonstrated relative toboth IEEE 802.11b and IEEE 802.11e. We showthrough analysis and extensive simulations thatSticky CSMA/CA achieves more efficient mediumutilization than IEEE 802.11e and can be used toprovide the required QoS in terms of bandwidth,delay and delay jitter to real-time flows. The under-lying reason is that this scheme obviates the need formedium contention for every frame that a nodetransmits, exploiting the predictable and periodicnature of the high priority traffic. This approach sig-nificantly reduces the probability of collision andthe overhead due to the backoff required for colli-sion avoidance for every frame in IEEE 802.11.We also show that, along with efficient support of significantly more real-time flows, the performancein terms of throughput achieved for the low prioritydelay-insensitive traffic is comparable to that of IEEE 802.11. These encouraging results indicatethat even for applications that do not exhibit peri-odicity and constant data rates naturally (e.g.,video, or even high-speed  data pipes  in a wirelessbackhaul), it may be useful to artificially imposeperiodicity and predictability to improve the effi-ciency of medium access. Detailed investigation of cross-layer architectures that shape variable ratereal-time traffic to take advantage of StickyCSMA/CA is beyond the scope of this paper. How-ever, we do provide some discussion as to how thismight be done for applications such as video inSection 6.The rest of the paper is organized as follows. Sec-tion 2 describes related work. The design of StickyCSMA/CA is described in Section 3. In Section 4, we present an approximate analysis to obtaininsight into the performance of IEEE 802.11 andSticky CSMA/CA. Section 5 presents the simulationresults obtained in mesh networks with line and gridtopologies. We conclude with a discussion of vari-ous design and application aspects of StickyCSMA/CA in Section 6. Note that we use the termsVoIP and voice interchangeably throughout thispaper. 2. Related work In the past few years, a considerable amount of work has addressed the area of MAC layer designfor providing the required QoS to voice, multimediaand data applications over wireless networks. Wediscuss some of the proposed approaches next.The IEEE 802.11 standard MAC sublayer pro-vides two different access mechanisms: the Distrib-uted Coordination Function (DCF), and the PointCoordination Function (PCF) [5]. PCF is a central-ized approach to perform bandwidth reservations,which splits time into a contention-free period(CFP) and a contention period (CP). A pollingscheme controlled by a Point Coordinator thatresides in the Access Point arbitrates channel accessduring the CFP. PCF is not suited for multihopwireless networks due to the requirement of central-ized control and the Point Coordinator at theAccess Point. The Distributed Coordination Func-tion (DCF) is based on CSMA/CA for frame trans-missions and a random backoff mechanism to avoidpacket collisions. We describe this scheme in moredetail in Section 3. DCFs drawback is that it doesnot provide service differentiation. Due to lack of both medium access priorities and QoS supportfor different applications, DCF is not suited for sup-porting real-time applications.The IEEE 802.11e standard extends the IEEE802.11 framework by including mechanisms for ser-vice differentiation [6]. Four access categories (AC),mapped to eight traffic priorities, are defined forIEEE 802.11e. These ACs correspond to differentvalues of the following parameters: minimum con-tention window size (CW min ), maximum contentionwindow size (CW max ), and the Arbitration Inter-frame Space (AIFS) (time-interval between idletransition of the medium and the start of channelaccess or backoff). A lower value of these parame-ters causes shorter backoff intervals or wait periodsbefore medium access, thereby prioritizing traffic.IEEE 802.11e has different queues for differentACs. It also provides an optional token-like mecha-nism called TXOP (Transmission Opportunity) tosupport packet bursts, where a node that hasobtained access to the medium can send multipleframes for an AC, up to a maximum time-limit,without further contention. This contention-freebursting mechanism aids in transmission of burstytraffic and improves medium utilization. One of the drawbacks of IEEE 802.11e is the lack of assured QoS for individual flows. IEEE 802.11ecan only provide service differentiation amongdifferent ACs, but QoS degrades in the presence of multiple contenders in the same AC because of med-ium access contention with equal priority for every 746  S. Singh et al. / Ad Hoc Networks 5 (2007) 744–768  packet belonging to the same AC. The underlyingreason for lack of support of a deterministic QoSin IEEE 802.11e and IEEE 802.11 is that everypacket requires contention for the medium in theseschemes, and no attempt is made to exploit the (nat-ural or possibly imposed) predictability of packettransmissions to minimize contention losses.Blackburst [7] is a scheme based on modifiedIEEE 802.11 CSMA/CA designed to provide QoSto real-time applications. In this scheme, a nodewith real-time data contends for medium access bysending an energy burst (called a blackburst) fortime proportional to the wait time of the node.The node with the longest burst wins the contentionand transmits a frame. Blackburst does not addressthe hidden terminal problem and requires that thenodes have the capability to jam the medium.Another distributed MAC scheme derived fromIEEE 802.11 DCF is Distributed Fair Scheduling(DFS) [8], which is based on Self-Clocked FairQueuing (SCFQ) [9]. DFS achieves service differen-tiation by assigning different backoff intervals topackets that belong to different flows based on theweights assigned to the flows. This feature ensureshigher throughput to flows with higher weights,and fairer overall allocation of bandwidth as com-pared to IEEE 802.11 DCF. DFS does not considerthe delay bounds of real-time packets, nor does itaddress mechanisms for determining appropriateweights for different flows, both of which greatlyinfluence the performance.Multiple Access Collision Avoidance with Piggy-backReservations(MACA/PR)[10]isaschemethatsupports bandwidth reservations for real-time traf-fic.In this scheme, each node maintains the real-timescheduling information of the neighboring nodes inits reservation tables (RT) by overhearing the datapackets or ACKs. The global reserved slot informa-tion is obtained by periodic RT exchange amongneighbors.TheRTexchangetakescareofthehiddenterminal problem. The drawbacksof MACA/PR arethe piggybacking-based reservation approach andthe overhead of periodic RT exchange.A few recent proposals attempt to take advan-tage of TDMA schedules for reducing interferenceand for fair resource allocation over CSMA basednetworks [11,12]. The Overlay MAC Layer (OML)[11] is an access control and scheduling scheme thatpartitions time into equal size slots and allocatesthese slots among loosely synchronized contendingnodes. Though OML implements temporal fairnessand reduces interference by improving the predict-ability of medium access among nodes, the coarsetime-slot based resource allocation does not addressthe QoS requirements of different applications.Another interesting MAC framework proposed inthe context of sensor networks is ZMAC [12].ZMAC exploits TDMA schedules among locallysynchronized neighbors to improve medium utiliza-tion and reduce packet collisions among two hopneighbors in a CSMA network operating under highcontention. Under low contention, all the nodescontend for a slot but the slot-owner nodes have ahigher priority over their neighbors by virtue of ashorter contention window. This scheme incurs ini-tial schedule allocation overhead in the networkdeployment phase and, because it was designed fora sensor network, it does not consider service differ-entiation among different applications for QoSsupport.To the best of our knowledge, the proposedSticky CSMA/CA scheme is the first approach thatexploits the characteristics of real-time applicationsto devise medium access control strategies thatreduce delay and delay jitter. Exploiting the naturalperiodicity of VoIP is shown (in the succeedingsections) to lead to large capacity gains relative toIEEE 802.11. This motivates future work (see thediscussion in Section 6) in taking this approachone step further, by imposing artificial regularityat the application layer in order to obtain theenhanced QoS obtained using Sticky CSMA/CAmedium access. 3. The sticky CSMA/CA protocol In this section, we describe the Sticky CSMA/CAprotocol. We briefly outline conventional CSMA/CA and introduce history considerations intoCSMA/CA. We then describe the carrier sensingmechanism and discuss the operation of StickyCSMA/CA for real-time and delay-insensitivetraffic. 3.1. Conventional CSMA/CA The IEEE 802.11 DCF uses CSMA/CA for datapacket transmission, along with a random backoff mechanism to avoid collisions. A node that has aframe to transmit senses the transmission activityinthemedium.Ifthemedium is freeforadistributedinterframe space (DIFS) interval, the frame is trans-mitted. If the medium is sensed as busy, the nodewaitsuntilthemediumisfreeforafixedtimeinterval S. Singh et al. / Ad Hoc Networks 5 (2007) 744–768  747  (DIFS if the last frame was received without anytransmission errors, or extended interframe space(EIFS) otherwise). After the medium is sensed idlefor a DIFS/EIFS interval, the node generates abackoffcounter b i  ,whichisapseudo-randomintegerwith a uniform distribution in the interval [0,CW i  ],where CW i   = min(CW max ,2 i   1 (CW min  + 1)    1) forthe  i  th transmission attempt for a frame. The nodethen decrements the backoff counter  b i   by one forevery  slot width  interval if the medium remains idle.If the medium becomes busy before  b i   reaches zero,the backoff procedure is frozen and is continuedafter the medium is sensed idle again for a DIFSinterval. When the backoff counter reaches zero,the node transmits the frame. If the transmissionfails and the ACK is not received from the receiver,then the node moves to the next backoff stage ( i   + 1)and repeats the procedure. Fig. 1 describes the back-off procedure for two nodes, A and B, that can heareach other. 3.2. Introducing history into CSMA/CA CSMA/CA with history incorporates the historyof the recent transmission activity in the mediuminto the conventional CSMA/CA mechanism forpacket transmissions. The primary difference fromconventional CSMA/CA is that the medium activityhistory information is used to infer the time win-dows that are occupied by periodic real-time flows.Time windows with periodic transmissions are con-sidered  reserved   by the existing real-time flows, andhence there is no contention for these time windows.We assume that all the realtime flows are periodicwith a common period. The most relevant exampleof such flows is voice applications, which generateperiodic data based on the codec used (e.g., ITU-T G.711 codecs periodically generate fixed sizedpackets at a data rate of 64 Kbps).We define a  cycle  as the time period between twoconsecutive packet transmissions of any ongoingreal-time session. Therefore, the transmission activ-ity over the last few cycles can be used to infer thereal-time flow reservations of the medium. All thenodes in the network maintain a  medium activitymap  containing the medium busy/free state infor-mation over a fixed number of past cycles. A nodeinvokes conventional CSMA/CA to find a transmitopportunity, taking into account its medium activ-ity map to ensure that it does not interfere withany existing real-time flow. A backoff mechanismsimilar to IEEE 802.11e, but with smaller conten-tion window parameters, is followed to avoid colli-sions. As an example, consider a three nodenetwork with a bidirectional real-time flow betweennodes A and B. Fig. 2 shows the activity maps of themedium at nodes A, B and C, assuming that node Ccan hear nodes A and B. 3.3. Sticky CSMA/CA We view continuous time in terms of time-slots.As mentioned before, we assume that the cycle timeis the same for all the nodes in the network. Notethat since we assume an asynchronous framework,the cycles can start at different times at different DIFS Node B has packet to sendNode A has packet to send TransmitBusyTransmitBackoff SlotsTransmitBusy SIFS DATAACKDATABusyDATA DIFS ACKACK Node ANode B Node A has packet to send DIFSDIFS Backoff for Node BBackoff for node A Fig. 1. CSMA/CA: Backoff mechanism. ABABABAB Cycle Time Activity Map of BActivity Map of A AB Activity Map of CBusyBusy C Fig. 2. Activity map: nodes A and B have a bidirectional real-time flow between them. Node C is a neighbor of nodes A and B.The activity maps of nodes A, B and C contain reservations forthe real-time flow between nodes A and B. Note that the cyclesneed not start at the same time.748  S. Singh et al. / Ad Hoc Networks 5 (2007) 744–768
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks