In a slow fading environment, the carrier sense range is not constant, so there is not a constant set of hidden terminals for a mobile station. The probability of capture with a set of interferers is not a fixed value either, and it fundamentally affects the loss rate and throughput of the whole network. We estimate the expectation of the capture probability in a single hop ad hoc network and incorporate it with our previously proposed model for 802.11 DCF that considers the time-varying nature of carrier sensing. The system throughput is then derived from an individual station's point of view. The model is verified against simulations, and extensive numerical experiments are performed to demonstrate its application.

We present a model that predicts the saturated single-hop performance of IEEE 802.11 ad hoc network in the face of the physical capture effect under a block-fading Rayleigh channel. Based on an estimate of the frame delivery rate and a fixed point iteration algorithm, we devise an efficient control on the rate of convergence and a wise selection of the interferer sets that significantly affect the final results, so as to overcome the explosive time complexity of the iteration algorithm. These enhancements achieve up to two orders of magnitude speedup for large ad hoc networks with minimal and controllable prediction error, so that large scale Monte Carlo experiments for various distributions are made possible.

Physical Carrier Sensing plays a crucial role in the effectiveness of CSMA-based MAC protocols, yet its properties and impact on the system performance under slow fading channel have not been well understood. We demonstrate that carrier sensing can be highly unreliable even within the "carrier sensing range" and the channel is largely stable during a transmission between slowly moving mobile stations. Then we formulate the carrier sensing outage probability between competing mobile stations and propose a model to estimate the frame error rate and normalized throughput of a saturated IEEE 802.11 DCF single-hop ad-hoc network. Our model is validated via extensive simulations using Qualnet. The numerical and simulation results reveal substantial degradation in system performance with a small amount of carrier sensing outage.

Continuing the process of improvements made to TCP through the addition of new algorithms in Tahoe and Reno, TCP SACK aims to provide robustness to TCP in the presence of multiple losses from the same window. In this paper we present analytic models to estimate the latency and steady-state throughput of TCP Tahoe, Reno, and SACK and validate our models using both simulations and TCP traces collected from the Internet. In addition to being the first models for the latency of finite Tahoe and SACK flows, our model for the latency of TCP Reno gives a more accurate estimation of the transfer times than existing models. The improved accuracy is partly due to a more accurate modeling of the timeouts, evolution of cwnd during slow start and the delayed ACK timer. Our models also show that, under the losses introduced by the droptail queues which dominate most routers in the Internet, current implementations of SACK can fail to provide adequate protection against timeouts and a loss of roughly more than half the packets in a round will lead to timeouts. We also show that with independent losses SACK performs better than Tahoe and Reno and, as losses become correlated, Tahoe can outperform both Reno and SACK.

While it is well known that second order scaling in network traffic can lead to larger queueing delays, higher drop rates and extended periods of congestion, reducing the scaling exponents has remained an open problem. In this paper we evaluate some techniques to reduce the degree of scaling in TCP traffic, specifically by reducing two related causes: (1) timeouts and exponential backoffs; and (2) burstiness and ACK compression. We propose a simple modification to the RED algorithm, and show that it can lead to significant reductions in both multi and mono fractal properties of TCP traffic as compared to the currently implemented active and passive buffer management policies. We then evaluate TCP pacing and show that it too can reduce the multi and mono fractal scaling of traffic. We also show that though our techniques are aimed at small time-scale TCP related causes of scaling, they are also effective in reducing the degree of self-similarity in traffic even when application and user level causes are also present, as long as TCP is used as the underlying transport protocol.

In this paper we present analytic models to estimate the latency and steady-state throughput of TCP Tahoe, Reno and SACK and validate our models using both simulations and TCP traces collected from the Internet. We also conduct a study comparing the performance of these versions of TCP under different loss scenarios. In addition to being the first models for the latency of finite Tahoe and SACK flows, our model for the latency of TCP Reno gives a more accurate estimation of the transfer times than existing models. Our models show that under the losses introduced by the droptail queues which dominate most routers in the Internet, current implementations of SACK fail to provide adequate protection against timeouts and a loss of roughly more than half the packets in a round will lead to timeouts. We also show that with independent losses, SACK performs better than Tahoe and Reno and as losses become correlated, Tahoe can outperform both Reno and SACK.

The complexity and dynamics of the Internet is driving the demand for scalable and effective network control. This paper proposes a collaborative on-line simulation architecture to provide pro-active and automated control functions for networks. The general model includes autonomous on-line simulators which continuously monitor/model the network conditions and execute a search in the parameter state space for better settings of the protocol parameters. The protocol parameters are then tuned by the on-line simulation system. We describe the building blocks of this architecture and investigate the implementation challenges in the areas of network modeling, on-line simulation and parameter search. We also discuss the applicability of this system and present the simulation and test results of a preliminary implementation.

This paper analyzes the throughput for an adaptive packet radio network (PRN). The proposed adaptive OFDM spread spectrum (OFDM-SS) system can trade off system processing gain (i.e. user data rate) for transmission quality under changing channel conditions. Classic throughput analysis for fixed and random access schemes is extended for this proposed adaptive PRN. The focus is on pure-ALOHA and nonpersistent CSMA (NP-CSMA) systems. The paper introduces a method to analyze network throughput with variable packet durations due to variable user data rate. The large improvement from the adaptive system compared to the conventional fixed rate counterpart is demonstrated by various mobile user population profiles and radio propagation path loss models.

The development of broadband networks has led to the possibility of a wide variety of new and improved service offerings. Packetized video is likely to be one of the most significant high-bandwidth users of such networks. The transmission of variable bit-rate (VBR) video offers the potential promise of constant video quality but is generally accompanied by packet loss which significantly diminishes this potential. We study a class of error recovery schemes employing forward error-control (FEC) coding to recover from such losses. In particular, we show that a hybrid error recovery strategy involving the use of active FEC in tandem with simple passive error concealment schemes offers very robust performance even under high packet losses. We discuss two different methods of applying FEC to alleviate the problem of packet loss. The conventional method of applying FEC generally allocates additional bandwidth for channel coding while maintaining a specified average video coding rate. Such an approach suffers performance degradations at high loads since the bandwidth expansion associated with the use of FEC creates additional congestion that negates the potential benefit in using FEC. In contrast, we study a more efficient FEC application technique in our hybrid approach, which allocates bandwidth for channel coding by throttling the source coder rate (i.e., performing higher compression) while maintaining a fixed overall transmission rate. More specifically, we consider the performance of the hybrid approach where the bandwidth to accommodate the FEC overhead is made available by throttling the source coder rate sufficiently so that the overall rate after application of FEC is identical to that of the original unprotected system. We obtain the operational rate-distortion characteristics of such a scheme employing selected FEC codes. In doing so, we demonstrate the robust performance achieved by appropriate use of FEC under moderate-to-high packet losses in comparison to the unprotected system.

In this paper, we explore the design of forward error control (FEC)-based error concealment schemes for digital video transmission on ATM networks. In particular, we study the impact of code selection on the overall performance and provide a judicious code selection strategy. The use of FEC provides an active and powerful means of recovery from packet loss which is particularly useful when the encoded video material has high motion and scene changes. The best technique for applying FEC is to throttle the source coding rate so that the overall transmission rate after FEC application equals the original unprotected rate. However, the resulting performance then depends on the particular code selected. A well-chosen code provides good protection while allowing little sacrifice in quality and at the same time satisfies specified delay constraints. Our results show that a single code is generally insufficient to provide good performance under all operating conditions. However, a small group of codes can be preselected, using the efficient code-selection strategy described here, which will provide efficient and robust performance over a wide range of channel conditions. We show that this simple code selection strategy is sufficient to select codes judiciously for a wide range of operating conditions and constraints. Employing this selection strategy, we demonstrate that moderate length codes are sufficient to provide good performance while meeting the imposed delay constraint.

We develop parameters and results for a set of traffic models which emulate the traffic patterns at the packet and buffer levels. We show that traffic models at these levels are dependent on the network capacity as well as source-induced bottlenecks such as buffer reads and writes. We propose a pragmatic approach which uses three variations of a simple two-state Markov superposition model to describe the buffer and packet level view of the traffic under different bottleneck conditions. We apply these models to actual network traffic sources as measured on a medical network and evaluate the impact of changing bottlenecks in network transfers. Our data and results emphasize the sensitivity of any traffic model to the underlying machine capabilities and the timescale of interest. These models can be used to characterize a wide range of traffic types, and allow relatively simple analytic and simulation implementation.

A new protocol, fair distributed queue (FDQ), suitable for very high-speed metropolitan-area networks (MANs), is presented. FDQ is a slotted system implemented on a unidirectional fiber bus. It has similarities to distributed queue dual bus (DQDB), the IEEE 802.6 Standard for MANs, including the bus topology and same nodal hardware. Like DQDB, FDQ achieves full throughput efficiency independent of the bus length, the transmission speed, and the number of nodes. Unlike DQDB, FDQ allocates equal bandwidth under heavy load to all active users in a time period less than or equal to the round-trip propagation delay without wasting bandwidth. Its delay characteristics are studied via simulation and compared to DQDB. FDQ has lower average delays under Poisson load than DQDB with or without the bandwidth balancing (BWB) mechanism. Two distinct implementations of priority levels are given and their characteristics are discussed. It is shown that FDQ's delay and throughput characteristics are little affected with increasing distances or transmission rates. Thus, FDQ possesses excellent scalability properties which allow its total length to extend over 100 km and transmission rate well above 1 Gb/s.

The control of source-coded traffic at a multiplexer has been a topic of extensive research. Traditional approaches typically use feedback information on the buffer level in designing the control policy. While important, buffer levels capture only part of the information about the overall system state. By setting up this problem as a Markov decision process, the authors show that using information on the state (activity) of the sources, in addition to the buffer level, can result in significant improvements over traditional approaches. They demonstrate this for a multiplexer fed by /spl mu/-law encoded voice sources. Some of the scenarios studied exhibit a reduction in distortion exceeding 35%. In general, the improvement is heavily dependent on the correlation statistics of the sources. Emulations validate the analysis. The form and characteristics of the optimal control policies are also discussed.

The exhaustive cycle-gated (ECG) scheme was proposed as a high throughput access mechanism for high speed bus protocols like Expressnet and Fasnet. However, the ECG scheme exhibits unfairness to the downstream station which suffers higher mean and variance of waiting time. In the paper the authors propose and analyze a new cycle-gated scheme, the shifting cycle-gated (SCG) scheme, on the Expressnet topology. They demonstrate that the SCG scheme is fair to all the stations in the sense that the mean and variance of the waiting time are the same for all stations, irrespective of the spatial distribution of the stations on the bus and the service time distribution of the packets at the stations, for uniform load. The SCG scheme achieves this fairness by shifting the order of service of stations from one cycle to the next. The analysis methodology uses space-time diagrams to derive expressions for the moment generating function, mean and variance of the waiting time under assumptions of independent nonsymmetric Poisson arrival processes at N stations on the bus. Extensive numerical results illustrate the behavior of the SCG protocol.>

Fair distributed queue (FDQ) is a high speed metropolitan area network proposed by Kabatepe (1992). FDQ has fair throughput, and delay characteristics and is a highly scalable protocol in that its performance is little affected by growing networks sizes, and/or transmission speeds. While FDQ allocates equal bandwidth to all active nodes, the authors focus on dividing the capacity arbitrarily among the active nodes. Under heavy load, this would result in nodes achieving throughput rates equal to their allocated bandwidths. Under normal load conditions, they aim to provide equal quality of service to the nodes in terms of message delay, if their arrival rates turn out to be equal to their allocated bandwidths. They present the bandwidth allocation FDQ (BA-FDQ) protocol which achieves this objective subject to propagation delays. The delay characteristics of BA-FDQ are compared via simulation with FDQ, DQDB and DQDB with BWB under symmetric load (an important special case in the absence of known arrival rates). They also consider arbitrary bandwidth allocations and study the delay characteristics of BA-FDQ by simulation. The studies show that BA-FDQ makes the mean message delays of individual nodes close to each other as intended for transmissions on one of the buses.>

A new protocol, fair distributed queue (FDQ), suitable for very high speed metropolitan area networks (MANs), is presented. FDQ is a slotted system implemented on a unidirectional fiber bus. It has similarities to the distributed queue dual bus (DQDB) protocol. FDQ achieves full throughput efficiency independent of the bus length, the transmission speed, and the number of nodes. FDQ allocates equal bandwidth under heavy load to all active users in a time period less than or equal to the round-trip propagation delay without wasting bandwidth. Its delay characteristics were studied via simulation and compared to DQDB. FDQ has lower average delays under a Poisson load than the DQDB protocol with or without the bandwidth balancing mechanism. The implementation of priority levels and detailed timing structure of the protocol are also described. It was shown that FDQ's delay and throughput characteristics were only slightly affected by increasing distances or the number of nodes.>

The distributed queue dual bus (DQDB) standard is studied under heavy load conditions. The DQDB protocol for asynchronous traffic is reviewed. The network model and analysis are presented when there are two active nodes. Analytic expressions are derived for the steady-state nodal throughputs and the average value of the request counters of inactive nodes. The three-station case is considered by providing an accurate approximation for the situation when the third node is in between the two initially active nodes. Simulation results are given for comparison. The effect of the position of a node was studied via simulation in the three-station case. The case when one of the active nodes becomes inactive in a network with three initially active nodes is analyzed. The state the network assumes is studied in terms of nodal throughputs after one of the nodes turns off, and the impact on the request counters of the inactive nodes are investigated.>

The transient behavior of the Fiber Distributed Data Interface (FDDI) protocol is analyzed, under the assumption of a heavy-load for a single asynchronous priority level. The analysis leads to a simple characterization of the asynchronous transmission times for the different stations. From this characterization, an algorithm to calculate the token rotations and times at which different stations in the ring begin to transmit asynchronous data is derived. Simulation results show that the behavior predicted by the algorithm is approached under heavy Poisson asynchronous load in the network.>

An analytical model is applied to predict the performance of the FDDI (Fiber Distributed Data Interface) network in satisfying the delay constraints on the synchronous-class data frames. An example which illustrates the application of the analytic work and provides insight into the relationships between network performance and the negotiated parameter values of the FDDI protocol is given. In particular, the example demonstrates that while the current FDDI priority scheme guarantees a station will receive the token within a specified time, it does not guarantee that all waiting synchronous packets will meet their deadlines.>

A Markovian model is developed for the analysis of an integrated voice/data local area network protocol. This protocol is a variation on a protocol proposed by N.F. Maxemchuk (1982). In this protocol, voice accesses the channel initially using CSMA/CD (carrier-sensing multiple access with collision detection) and thereafter using TDMA (time-division multiple access). Data uses CSMA/CD; priority is given to voice. Using this model, the throughput/delay characteristics for data users is derived.>

The problem of finding a detector nonlinearity that maximizes the efficacy (or asymptotic processing gain) over a class of suboptimal nonlinearities is considered. It is shown that this efficacy maximization problem is essentially the same as the problem of finding the minimum-mean-square-error approximation to the locally optimal detector nonlinearity. This result is compared with some intuitive ideas about suboptimal detection.

The Middleton Class A narrow-band non-Gaussian noise model [9]-[12] is examined. It is shown that this noise model (which is known to fit closely a variety of non-Gaussian noises) can itself be closely approximated by a computationally much simpler noise model. It is then shown by numerical examples that, for the problem of locally optimum detection, the simplest form of this approximation yields nearly optimal (asymptotic) performance. The performance of other simple suboptimal threshold detectors in Class A noise is also examined. Finally, a useful relationship between the Class A model and the ε-mixture model is developed.

A minimax formulation is considered for the problem of designing robust linear causal estimators of linear functions of discrete-time wide-sense stationary signals when knowledge of the signal and/or noise spectra is inexact. The solution is given (under mild regularity conditions) in terms of a least favorable pair of spectra, thus reducing the minimax problem to a direct maximization problem which in many cases can be solved easily. It is noted that this design method leads, in particular, to robustn-step predictors, robust causal filters, and robustn-lag smoothers. The method of design is illustrated by a thorough development of the special case of one-step noiseless prediction. Further, solutions are given explicitly for the problem of robust causal filtering of an uncertain signal in white noise, and numerical examples are given for this case which illustrate the effectiveness of this design.

Thep-point uncertainty class (also known as Sakrison's class b) is considered. Although the p-point class is not a2-alternating Choquet capacity class, it is shown how many of the robust signal processing and communication theory results which have been developed for capacity classes can be applied to thep-point class by embedding it in a slightly larger "extendedp-point class."

A maximin approach is applied to the problem of detecting a point target in white noise and clutter. That is, the reverberation scattering function (which characterizes the clutter) is not assumed to be known exactly. The problem becomes one of finding a signal-filter combination which provides the best possible lower bound on detector performance. A "quasi-universal" solution is obtained for this problem which is applicable in many practical situations. For many other situations a general (but preliminary) theory is developed.