Many virtual circuit service communications networks such as SNA employ virtual circuit transmission method inside the subnet. An essential feature of such networks is that the sequence in which messages are transmitted is maintained throughout the route from source node to the destination node. When there are multiple links connecting two intermediate nodes in the route and the messages are of different lengths, then it is possible that the messages complete transmission at the next node out of sequence. These messages then have to be resquenced, i.e. put in the right order, in order to provide a virtual circuit service. The resequencing operation introduces an additional delay in transmission which may be significant. In this paper the probability distribution of the resequencing delay is obtained for the M/M/m system. Simple expressions for the mean and coefficient of variation of the resequencing delay are also provided. It is shown through a variety of numerical examples that the resequencing delay is likely to be a significant component of the overall response time. Some interesting aspects of dependence of the mean resequencing delay on system parameters are studied analytically.

Response Time Preservation (RTP) is introduced as a general technique for developing approximate analysis procedures for queueing networks. The underlying idea is to replace a subsystem by an equivalent server whose response time in isolation equals that of the entire subsystem in isolation. The RTP based approximations, which belong to the class of decomposition approximations, can be viewed as a dual of the Norton's Theorem approach for solving queueing networks since it matches response times rather than throughputs. The generality of the RTP technique is illustrated by developing solution procedures for several important queueing systems which violate product form assumptions. Examples include FCFS servers with general service times, FCFS servers with different service times for multiple classes, priority scheduling, and distributed systems.

Token rings and multipoint polled lines are two widely used network interconnection techniques. The general concept of cyclic allocation processes is defined and used to characterize token passing and polling in these networks. Scan time, the time to poll all nodes at least once, is an important quantity in the response time analysis of such networks. We derive expressions for the mean and variance of scan times using a direct, operational approach. Resulting expressions are general and are applicable to both exhaustive and non-exhaustive service. The effect of higher level protocols is easily incorporated in the analysis via calculations of constituent quantities. The expression for mean scan time is exact and depends only on the means of message transmission times and arrival rates. The approximate analysis of variance takes into account the correlation between message transmissions at different nodes. Expected level of accuracy is indicated by an example.

An important problem in queueing network modeling is that of characterizing and analyzing relationships among alternative models of a single system. The problem is approached by developing the concept of a state space transformation, which is a mechanism for expressing the way one model can be mapped into another. After discussing state space transformations in general terms, some important transformations are presented. The usefulness of the technique is demonstrated by developing state space transformations for the shadow CPU technique for analyzing preemptive priority scheduling and the aggregate server method for modeling serialization delays.

Method for Analyzing Computer SystemsThe aggregate server method is an approximate, iterative technique for analyzing the delays that programs encounter while waiting to enter critical sections, non-reentrant subroutines, and similar software structures that cause processing to become serialized.The method employs a conventional product form queuing network comprised of servers that represent actual I/O devices and processors, plus additional aggregate servers that represent serialized processing activity.The parameters of the product form network are adjusted iteratively to account for contention among serialized and nonserialized customers at each physical device.The algorithm is developed for single-class closed queuing networks with load-independent servers employing processor sharing scheduling disciplines.Validations based on comparisons with exact numerical solutions are presented, and some factors affecting the accuracy of the method are discussed.Extensions to multiclass queuing networks, variable rate servers, and other scheduling disciplines are also suggested.