The n‐ary stack algorithm for the wireless random access channel

The emergence of wireless and personal communication networks has brought random access protocols for packet radio networks back to the research forefronts. Most such protocols are based on the ever popular ALOHA protocol. Unfortunately, this protocol is inherently unstable and requires sophisticated schemes to stabilize it. Another class of random access schemes, called limited sensing or stack algorithms, has been proposed that is stable and allows for the dynamic incorporation of new stations into the network. In this paper, we will review the simple to implement n-ary stack algorithm, and we will study its performance under various system parameters in the presence of capture, and also in the presence of feedback errors. Finally, we will investigate its maximum system throughput under various traffic generation processes. This revised version was published online in June 2006 with corrections to the Cover Date.     

A journey through the DQDB network literature

The Distributed Queue Dual Bus (DQDB) network has been adopted as the subnetwork for the IEEE 802.6 metropolitan area network (MAN) standard. Since its original proposition a few years back, DQDB has attracted significant attention because of the simplicity of its medium access control (MAC) protocol. The intense scrutiny that DQDB has been subjected to has lead to the identification of a number of its potential problems, and a number of “add-on” strategies have been proposed to “fix” such problems. Moreover, a number of architectural variations have also been proposed to improve the network behavior. Since there has been a literature explosion on DQDB over the past few years, this article is intended to extract the significant features of various DQDB-based investigations, and to present them in an unified manner.     

airConn: A framework for tiered services in public wireless LAN hot spots

Access to the data services via wireless LANs at private and public hot spot sites is becoming commonplace. The goal of the airConn project is to define an architecture and a prototype implementation that enable the provision of premium and non-premium service tiers for both transient and nontransient users of wireless hot spots. airConn provides for dynamic renegotiation of service tiers and facilitates various billing modes. Thus, it enables service providers to increase their revenue opportunities via multiple flexibility manageable service offerings.     

Jitter calculus in ATM networks: multiple nodes

We provide simple techniques for estimating the end-to-end jitter incurred by a periodic traffic in an asynchronous transfer mode (ATM) network. Our analysis is based on the careful examination of light and heavy traffic behavior of jitter incurred to a tagged renewal stream in a single node. Our results indicate that, in the heavy traffic as the number of nodes increases, the jitter distribution approaches to a limiting distribution which only depends on the behavior of the background traffic. We provide the functional equation satisfying this limit which bounds the moments of the jitter for arbitrary level of traffic. A simple approximation method based on the heavy and light traffic analysis of the jitter process is also provided and the results is supported by extensive simulation     

Seeing through black boxes: Tracking transactions through queues under monitoring resource constraints

The problem of optimal allocation of monitoring resources for tracking transactions progressing through a distributed system, modeled as a queueing network, is considered. Two forms of monitoring information are considered, viz., locally unique transaction identifiers, and arrival and departure timestamps of transactions at each processing queue. The timestamps are assumed to be available at all the queues but in the absence of identifiers, only enable imprecise tracking since parallel processing can result in out-of-order departures. On the other hand, identifiers enable precise tracking but are not available without proper instrumentation. Given an instrumentation budget, only a subset of queues can be selected for the production of identifiers, while the remaining queues have to resort to imprecise tracking using timestamps. The goal is then to optimally allocate the instrumentation budget to maximize the overall tracking accuracy. The challenge is that the optimal allocation strategy depends on accuracies of timestamp-based tracking at different queues, which has complex dependencies on the arrival and service processes, and the queueing discipline. We propose two simple heuristics for allocation by predicting the order of timestamp-based tracking accuracies of different queues. We derive sufficient conditions for these heuristics to achieve optimality through the notion of the stochastic comparison of queues. Simulations show that our heuristics are close to optimality, even when the parameters deviate from these conditions.     

PARO: Supporting Dynamic Power Controlled Routing in Wireless Ad Hoc Networks

This paper introduces PARO, a dynamic power controlled routing scheme that helps to minimize the transmission power needed to forward packets between wireless devices in ad hoc networks. Using PARO, one or more intermediate nodes called redirectors elects to forward packets on behalf of source–destination pairs thus reducing the aggregate transmission power consumed by wireless devices. PARO is applicable to a number of networking environments including wireless sensor networks, home networks and mobile ad hoc networks. In this paper, we present the detailed design of PARO and evaluate the protocol using simulation and experimentation. We show through simulation that PARO is capable of outperforming traditional broadcast-based routing protocols (e.g., MANET routing protocols) due to its energy conserving point-to-point on-demand design. We discuss our experiences from an implementation of the protocol in an experimental wireless testbed using off-the-shelf radio technology. We also evaluate the impact of dynamic power controlled routing on traditional network performance metrics such as end-to-end delay and throughput.     

A priority scheme for the IEEE 802.14 MAC protocol for hybridfiber-coax networks

In order to support quality-of-service (QoS) for real-time data communications such as voice, video and interactive services, multiaccess networks must provide an effective priority mechanism. The context of this work is the IEEE 802.14 standard for hybrid fiber coaxial (HFC) networks which has a shared upstream channel for transmissions from stations to the headend. This work presents a multilevel priority collision resolution scheme, which separates and resolves collisions between stations in a priority order, thereby, achieving the capability for preemptive priorities. We present a set of simulation scenarios which show the robustness and efficiency of the scheme, such as its ability to isolate higher priority traffic from lower priorities and to provide quick access to high-priority requests. In March 1998, a framework for handling priorities in the collision resolution process, which adopts a semantics similar to the semantics of our scheme, was included in the 802.14 standard     

A note on the conservation law for queues with batch arrivals

The conservation law formula for work-conserving queues with batch arrivals is derived for when the arrival instants of customers are assumed to constitute an arrivals see time averages (ASTA) process. The derivation is based on the analysis of the corresponding first-in first-out (FIFO) multiclass queue and its steady state. Hence, the mean work load in the queue at an arbitrary time instant can be equated with the mean time that an arbitrary customer has to wait in the FIFO queue