The distributed coordination function is one of three channel access control protocols specified by the IEEE 802.11 standard. In this paper we present a method of measuring DCF performance using a test bed built with off-the-shelf hardware. Performance is measured by normalized aggregate throughput as a function of the number of stations contending for channel access. We present measurements for both basic access and RTS/CTS access in fully-connected IEEE 802.11 g networks experiencing conditions of saturation. We compare our measurements to results from three analytic models and a simulator, all of which shared the same assumptions about the workload model and operation of DCF. For small networks the analytic models predict a much lower performance than shown through simulation and test bed experiments. As the network grows, so the measured performance deteriorates significantly faster than predicted by the analytic models. We attribute this to inaccuracies in the analytic model, imperfect channels and queuing. The simulation results fit the measured data with more accuracy, as the simulator makes fewer restrictive assumptions about DCF when compared to the analytic models. This is the first paper to provide a cross-comparison of test bed, simulation and analytic results for IEEE 802.11 g DCF performance.

The analytical model proposed in this paper aims at predicting the performance of software implementations which would be built according to the OSI basic reference model, The model uses the peer protocol standard of a layer as the reference description of an implementation of that layer. The model is basically a closed multiclass multichain queueing network with a processor-sharing center modeling process contention at the processor and a delay center modeling times spent waiting for responses from the corresponding peer processes. Each individual transition of the protocol constitutes a different class and each layer of the architecture forms a closed chain. Performance statistics include queue lengths and response times at the processor as a function of processor speed and the number of open connections. It is shown how to reduce the model should the protocol state space become very large. Finally, numerical results based upon the derived formulas are given.

A queuing analysis of a preemptive, priority-driven, time-sliced dispatcher algorithm, typical of those found in many time-sharing systems, is presented. A distinctive feature of the system being modeled is that a preempted task, when readmitted to the dispatcher, is reallocated a full time slice rather than the residual. The combination of preemption, time-slice renewal and class-dependent arrival and service rates places the analysis beyond that of the well-known FBN algorithms. The model is used to predict the behavior of the dispatcher algorithm under various workloads. The model reveals that, at high arrival rates, the time-slice renewal policy prevents processor bound tasks from being relegated to the lower priority queues, thereby severely degrading the throughput of tasks with short processor requirements.

Multiclass queuing network models of multiprogramming computer systems are frequently used to predict the performance of computing systems as a function of user workload and hardware configuration. This paper examines three different methods for incorporating operating system overhead in multiclass queuing network models. The goal of the resultant model is to provide an accurate account of the processing performance and the system CPU overhead of each of the several different types of jobs (batch, timesharing, transaction processing, etc.) that together make up the multiprogramming workload. The first method introduces an operating sysbtm workload consisting of a fixed number of jobs to represent system CPU overhead processing. The second method extends the jobs' CPU service requests to include explicitly the CPU overhead necessary for system processing. The third method employs a communicating set of user and system job classes so that the CPU overhead can be modeled by switching jobs from user to system class whenever they require system CPU service. The capabilities and accuracy of the three methods are assessed and compared against performance and overhead data measured on a Univac 1110 computer.

Let r be the total number of cycles required to complete a compromise merge of a given number of initial strings. Define row vectors m r - j and d j whose components represent the number and length respectively of strings at the end of the j th cycle of the merge. It is shown in this paper that there are asymptotic approximations to these vectors, which enables one to compute their respective components directly. Consequently, the number of cycles r can be computed directly, as in the case of the balanced merge.