OAR: An Opportunistic Auto-Rate Media Access Protocol for Ad Hoc Networks

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 delay jitter and 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.     

Ensuring latency targets in multiclass Web servers

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.     

Distributed Priority Scheduling and Medium Access in Ad Hoc Networks

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 backoff 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 termed multi-hop coordination so 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.