The IEEE 802.11 wireless media standard supports multiple frequency channels as well as multiple data rates at the physical (PHY) layer. In this paper, we introduce the multi-channel opportunistic auto rate (MOAR), an enhanced MAC protocol for multi-channel and multi-rate IEEE 802.11 enabled wireless ad hoc networks to opportunistically exploit the presence of frequency diversity (in the form of multiple frequency channels). The key mechanism of MOAR is that if the signal to noise ratio on the current channel is not favorable, mobile nodes can opportunistically skip to better quality frequency channels enabling data transmission at a higher rate. As channel separation for IEEE 802.11 is greater than the coherence bandwidth, different channels experience independent fading and hence there is a high probability that the skipping nodes will find better channel conditions on one of the other frequency channels. Each skip comes at the cost of resources spent in channel measurement since channel quality of different channels is not known a priori. Consequently, we devise an optimal skipping rule for MOAR which maps the channel conditions at the PHY layer to a MAC rule which allows each node to determine its optimum number of skips based on average channel conditions. Finally, we perform an extensive set of ns-2 simulations to evaluate the performance of MOAR and the impact of such factors as location distribution, channel conditions and error in channel measurements on the throughput gains offered by MOAR.

Two recent advances have resulted in significant improvements in Web server quality-of-service. First, both centralized and distributed Web servers can provide isolation among service classes by fairly distributing system resources. Second, session admission control can protect classes from performance degradation due to overload. The goal of this work is to design a general "front-end" algorithm that uses these two building blocks to support a new Web service model, namely, multiclass services which control response latencies to within prespecified targets. Our key technique is to devise a general service abstraction to adaptively control not only the latency of a particular class, but also to bound the interclass relationships. In this way, we capture the extent to which classes are isolated or share system resources (as determined by the server architecture and system internals) and hence their effects on each other's QoS. For example, if the server provides class isolation (i.e., a minimum fraction of system resources independent of other classes), yet also allows a class to utilize unused resources from other classes, the algorithm infers and exploits this behavior, without an explicit low level model of the server. Thus, as new functionalities are incorporated into Web servers, the approach naturally exploits their properties to efficiently satisfy the classes' performance targets. We validate the scheme with trace driven simulations.

The IEEE 802.11 wireless media access standard supports multiple data rates at the physical layer. Moreover, various auto rate adaptation mechanisms at the medium access layer have been proposed to utilize this multi-rate capability by automatically adapting the transmission rate to best match the channel conditions. In this paper, we introduce the Opportunistic Auto Rate (OAR) protocol to better exploit durations of high-quality channels conditions. The key mechanism of the OAR protocol is to opportunistically send multiple back-to-back data packets whenever the channel quality is good. As channel coherence times typically exceed multiple packet transmission times for both mobile and non-mobile users, OAR achieves significant throughput gains as compared to state-of-the-art auto-rate adaptation mechanisms. Moreover, over longer time scales, OAR ensures that all nodes are granted channel access for the same time-shares as achieved by single-rate IEEE 802.11. We describe mechanisms to implement OAR on top of any existing auto-rate adaptation scheme in a nearly IEEE 802.11 compliant manner. We also analytically study OAR and characterize the gains in throughput as a function of the channel conditions. Finally, we perform an extensive set of ns-2 simulations to study the impact of such factors as node velocity, channel conditions, and topology on the throughput of OAR.

Wireless emph ad hoc networks based on the IEEE 802.11 protocol can incur severe unfairness even in simple topologies. In particular, two topological properties that we define in a graph-theoretic framework and refer to as information asymmetry and perceived collisions result in significant performance degradations and unfairness. In this paper, we present the design and analysis of Distributed Wireless Ordering Protocol (DWOP), a distributed scheduling and media access algorithm targeted towards ensuring that packets access the medium in an order defined by an ideal reference scheduler such as FIFO, Virtual Clock, or Earliest Deadline First. In this way, DWOP enables QoS differentiation as well as fairness when combined with TCP. Our key technique is piggybacking head-of-line packet priorities in IEEE 802.11 control messages so that nodes can assess the relative priority of their own queued packets. With a graph-theoretic problem formulation, we design DWOP to achieve the exact reference ordering in fully connected graphs, and to have well-characterized deviations from the reference order in more complex topologies. A simple theoretical model indicates that the scheme attains rapid convergence for newly arriving nodes, and extensive simulations indicate that nearly exact reference ordering can be achieved, even in complex asymmetric and perceived collision topologies.

Providing quality of service in random access multi-hop wireless networks requires support from both medium access and packet scheduling algorithms. However, due to the distributed nature of ad hoc networks, nodes may not be able to determine the next packet that would be transmitted in a (hypothetical) centralized and ideal dynamic priority scheduler. In this paper, we develop two mechanisms for QoS communication in multi-hop wireless networks. First, we devise distributed priority scheduling a technique that piggybacks the priority tag of a node's head-of-line packet onto handshake and data packets; e.g., RTS/DATA packets in IEEE 802.11. By monitoring transmitted packets, each node maintains a scheduling table which is used to assess the node's priority level relative to other nodes. We then incorporate this scheduling table into existing IEEE 802.11 priority back-off schemes to approximate the idealized schedule. Second, we observe that congestion, link errors, and the random nature of medium access prohibit an exact realization of the ideal schedule. Consequently, we devise a scheduling scheme termedmulti-hop coordinationso that downstream nodes can increase a packet's relative priority to make up for excessive delays incurred upstream. We next develop a simple analytical model to quantitatively explore these two mechanisms. In the former case, we study the impact of the probability of overhearing another packet's priority index on the scheme's ability to achieve the ideal schedule. In the latter case, we explore the role of multi-hop coordination in increasing the probability that a packet satisfies its end-to-end QoS target. Finally, we perform a set of ns-2 simulations to study the scheme's performance under more realistic conditions.

Allocating resources for multimedia traffic flows with real-time performance requirements is an important challenge for future packet networks. However, in large-scale networks, individually managing each traffic flow on each of its traversed routers has fundamental scalability limitations, in both the control plane's requirements for signaling, state management, and admission control, and the data plane's requirements for per-flow scheduling mechanisms. In this paper, we develop a scalable architecture and algorithm for quality-of-service management termed egress admission control. In our approach, resource management and admission control are performed only at egress routers, without any coordination among backbone nodes or per-flow management. Our key technique is to develop a framework for admission control under a general "black box" model, which allows for cross traffic that cannot be directly measured, and scheduling policies that may be ill-described across many network nodes. By monitoring and controlling egress routers' class-based arrival and service envelopes, we show how network services can be provisioned via scalable control at the network edge. We illustrate the performance of our approach with a set of simulation experiments using highly bursty traffic flows and find that despite our use of distributed admission control, our approach is able to accurately control the system's admissible region under a wide range of conditions.