QUORUM – Quality of Service inWireless Mesh NetworksVinod Kone, Sudipto Das, Ben Y. Zhao and Haitao ZhengAbstract—Wireless Mesh Networks (WMNs) can provideseamless broadband connectivity to network users with low setupand maintenance costs. To support next-generation applicationswith real-time requirements, however, these networks must pro-vide improved quality of service guarantees. Current mesh proto-cols use techniques that fail to accurately predict the performanceof end-to-end paths, and do not optimize performance basedon knowledge of mesh network structures. In this paper, wepropose QUORUM, a routing protocol optimized for WMNsthat provides accurate QoS properties by correctly predictingdelay and loss characteristics of data traffic. QUORUM integratesa novel end-to-end packet delay estimation mechanism withstability-aware routing policies, allowing it to more accuratelyfollow QoS requirements while minimizing misbehavior of selfishnodes.Index Terms— QoS, Routing, Wireless MeshI. INTRODUCTIONWireless Mesh Networks (WMNs) have emerged as apopular alternative to provide last-mile connectivity to Inter-net users. Wireless mesh networks [1] are dynamically self-organizing and self-configuring networks where participat-ing nodes automatically establish and maintain connectivityamongst themselves. These networks are robust and have lowup-front and network maintenance costs. A WMN may bethought as a multi-hop Mobile Ad-hoc Network (MANET)with extended connectivity. They provide a cheaper alternativelast mile connectivity than ADSL or Cable networks, andhave been adopted by numerous academic and industrialdeployments [2]–[8].As deployments of WMNs continue to grow, we expectthese networks to have the ability to support the new gener-ation of streaming-media applications, such as Voice over IP(VoIP) and Video On-Demand (VOD) [9]. These applicationsrequire Quality of Service (QoS) guarantees in terms ofminimum bandwidth and maximum end-to-end delay. Mostexisting work on Wireless Mesh Networks rely on adaptingprotocols originally designed for mobile ad hoc networks, andoffer little support for QoS.In this paper, we propose a routing protocol for wirelessmesh networks that provides QoS guarantees to applicationsbased on metrics of minimum bandwidth (Bmin) and maximumend-to-end delay (Tmax). While issues such as end-to-endroute discovery have been studied in great depth for WMNsand MANETs [10], [11], our goal is to build a WMN routingprotocol that provides “strong” QoS guarantees. By “strong”we mean that our protocol will accept application requests fordesired bandwidth and delay bounds for a flow, and eitherreject the flow if such constraints are not possible, or acceptthe flow that satisfies those performance bounds at the time ofthe request. If and when a route is disrupted by a node or linkfailure, our protocol automatically detects the route breakages,and re-discovers alternate routes if they exist.This paper makes three key contributions. First, we proposea mechanism that accurately predicts the end-to-end delay ofa flow, and show how it can be integrated into flow setupto satisfy QoS requirements. Second, we define a robustnessmetric for link quality and demonstrate its utility in route selec-tion. This robustness metric supports “intelligent” routing thatnot only deals with communication gray-zones and fluctuatingneighbors [12], but also helps discourage selfish “Free-riding”behavior [13]. Finally, we perform extensive evaluation of ourprotocol in the Qualnet simulator under a variety of conditionsand metrics.The remainder of this paper is organized as follows. Sec-tion II describes previous work on routing and QoS sup-port in wireless networks. Second, Section III describes ournetwork model and design objectives, and highlights themajor challenges in providing strong QoS guarantees. Next,Section IV describes the details of the QUORUM routingprotocol. Finally, we describe our simulation setup and resultsin Section V and conclude in Section VI.II. RELATED WORKWireless networks has been an active area of researchinterest and a significant work has been done on routing inwireless networks [14]–[16] and MANETS [10], [11]. Butthere has been a relatively less focus on providing “strong”QoS guarantees for WMNs. Most of the existing work is eitherfocused on MANETs or WMNs which have multiple radios.A review of relevant literature shows that various approacheshave been taken to provide QoS guarantees.Some researchers advocate for a stateless approach [17],while others have advocated maintaining state at intermediatenodes [18]–[20]. Providing a stateless solution in [17], theauthors describe a way to achieve QoS routing without usingexplicit reservation mechanisms and give new distributedsolution to oscillation and collision of flows. This paperproposes QoS based on OLSR, and has both the advantagesand disadvantages of the underlying proactive routing protocol.Moving on to the stateful approaches, Chen et. al. [20]propose a Distributed QoS Routing Scheme where the pathis computed by the exchange of control messages, and thestate information kept at each node is collectively used to finda path. WMR [19] is another stateful protocol that has beenproposed to provide QoS enabled routing in WMNs and is2the result of modifying its MANET counterpart, AQOR [18]to the wireless mesh context. Both AQOR and WMR cannotprovide strong delay guarantees, since they perform delayestimation using Route Request (RREQ) and Route Reply(RREP) messages. Our experiments in Section V show thesedelay estimators to be highly inaccurate.Other approaches include use of channel switching [21]where APs use multiple channels and Mobile Hosts (MHs),upon detection of a QoS violation, switch channels to connectto another AP. Another approach [22] proposes clusteringof end hosts and use of orthogonal channels to reduce theeffect of interference. A very different method [22] suggeststhe use of a statistical mechanics technique called Annealing.In [22], the authors propose a new QoS routing protocol forWireless Mesh Networks. They use delay and bandwidth asthe QoS parameters and then use Mean Field Annealing forfinding a suitable path. MFNRS uses deterministic equationsto replace stochastic processes in Simulated Annealing (SA)& Saddle Point Approximation in the calculation of stationaryprobability distribution at equilibrium.Even though there has been some work in designing so-lutions for