A novel state-space approach is used to characterize the overload cycle behavior of a generalized bandwidth balancing (BWB) scheme for the distributed queue dual bus (DQDB) multiple access procedure. The author exploits the fact that each node and the bus can be modeled by a finite state machine and will have cycles in the state diagram. The cycles of interest are referred to as overload cycles and result when one or more nodes are simultaneously trying to access the bus as quickly as possible. The author determines the overload cycle invariants imposed by BWB and generalizes BWB to be any integral relationship between used and skipped empty segments. It is shown that the ordinary access-based priorities cannot work, without some additional cycle invariants, in a system employing bandwidth balancing since it is impossible to preclude service to an upstream low priority mode and generalized BWB is suggested as an alternative method for obtaining rate-based priority grades of service.>

The main new result in this paper is a simple expression for the variance of the waiting time for a token ring with an infinite number of stations, nonsymmetric Poisson traffic, deterministic ring delays, and virtually identical service distributions. These results can be considered as an approximation to the large ring where no individual station dominates the traffic. In the process, the exact equations for obtaining the variance of the waiting time for arbitrary traffics and service densities are found. In general, if there arennonsymmetric stations, about n3equations need to be solved.

This paper derives exact results for a token ring system with exhaustive or gated service. There areNnodes on the ring and control is passed sequentially from one to the next. Messages with random lengths arrive at each node and are placed on the ring when the control arrives at that node. Exhaustive service means that the queue at a node is empty before the token is released and gated means that only those messages in the queue at the arrival of the token are served at that cycle. Generating function recursions for the terminal service time (the total sojourn time of a token at a node) and, from this, joint cycle and intervisit times are derived. Using known results relating the marginal generating functions of the waiting time and the cycle and intervisit time, it is shown that theNmean waiting times at the nodes require the solution ofN(N - 1)and N2equations for the exhaustive and gated cases, respectively. The arrival processes are assumed to be Poisson with different rates and the service processes are general and different at each node. In addition the token overhead is allowed to have an arbitrary but independent distribution at each node. Explicit, simply programmed equations are given. It is shown, arguing from the form of the equations, that there is a conservation law in effect in this system. If the nodal mean waiting times are weighted by the relative intensity, defined here as the intensity weighted mean, then the sum takes on a particularly simple form and is independent of the placement of the nodes on the ring. When the service means at each node are equal, this quantity is just the system mean waiting time.

This paper introduces a new class of network design problems implementing an integrated teleconferencing environment consisting of a video space showing images of the participants, an audio space providing their voices, and a graphics space providing reference and discussion material for the conference. These various spaces provide services of differing quality and type. The problem posed is to design topologically optimal networks that are least costly and that will have the flexibility to carry conferences of differing service quality and type. The actual networks studied in this paper consist of the design of a private network for a single conference amongNidentical, but arbitrarily located, sites. Network designs will be minimum link-cost or constrained minimum link-cost optimal, where the first is minimal over all possible network topologies and the second is constrained to consider only those topologies that have the minimum number of links. For terrestrial systems, one of the interesting results is that classical network topologies such as rings and minimum spanning trees are optimal for some conference types. However, no topology is optimal for all types, and some topologies use their capacity very poorly when used for a type for which they were not optimized. Unlike terrestrial networks, satellite networks may be easily configured to have all of their capacity available for all conference types.

A new and flexible solution to the problem of multiple users accessing a single resource, such as communication bandwidth or composite object in memory, is derived. The means of communication consists of sending and receiving messages in known locations (or equivalently, mailboxes without queueing). Any particular user is able to deposit, and hence destroy, previous messages in a mailbox. It is assumed that exclusive access to a mailbox is supplied by an underlying system. The major results of this paper are: 1) a simple tree-based algorithm that guarantees • no user or group of users can conspire to prevent access by some other user to the resource; • only one user accesses the resource at a time; • if there are N users, an individual user is guaranteed access, when requested, to the resource in no more than N-1 turns; Knuth's solution [6] can delay a user up to 2** (N-1)-1 turns; 2) an extension of Dekker's algorithm (2 users) [2] that allows the relative rates of reservations for access to the resource to be proportional to a set of N integers. When a reservation is not being used by its ``owner,'' it will be assigned to another contending request. The assignment is optimal for periodic requests.

In a recent paper by Fayolle, Mitrani, and Iasnogorodski [2], some general multidimensional integral equations were derived in order to solve for the mean response time of each of several classes in a queue whose service discipline was weighted processor sharing. The arrival processes were Poisson. The weighting means that each job within a class k is given an amount of processing proportional to the priority weight gk associated with that class. For exponential service times, the general equations were solved. In this note, a simple observation allows use of the exponential solution directly for the case of hyperexponential servers. As a result, it is possible to state the following. •Characterization of a server in terms of its mean and coefficient of variation is not sufficient to predict even the mean response time for a class using weighted processor sharing. In unweighted or egalitarian processor sharing, only the mean is sufficient. •The Kleinrock conservation law [4] does not hold for nonexponential servers. Fayolie et al. [2] had showed that it did hold for exponential servers.

This paper presents an approximate analysis of a pure unslotted ALOHA random access with fixed-length packets and computes percentiles of delay for various throughputs. It introduces the concept of the burst ratio (mean packet interarrival time/maximum delay) of a source which allows a precise comparison with time division multiplexing (TDM) and indicates when ALOHA is the preferred access technique. The paper presents two curves that should be sufficient for design along with a simple computational procedure. Results are verified and augmented using simulation.

In this paper we compute the mean delay for an unslotted ALOHA random access channel for both fixed and variable length packets. The analysis is based on the concept of a user cycle and obtains steady state results. When the channel is "stable", the results seem quite accurate. The input parameters to the model are the number of users, the mean think time, and mean retransmission time. The model yields total traffic, throughput and delay but only the latter is emphasized here. Because of the steady state nature of the analysis, no information is obtained on stability. The results are verified by simulation.

This concise paper explores some of the boundaries in performance of slotted ALOHA systems by analyzing a simple and almost optimal centrally supervised control. Our control results in a very simple Markov chain model and allows an examination of stability, conditional waiting time distribution of transmitting terminals, and many other system measures. The key to the simplicity is to have a probability of successful packet transmission that is independent of the number of transmitting terminals. Regarding stability, recent papers have shown that a slotted ALOHA system with an infinite population of terminals producing packets at a Poisson rate λ/slot becomes saturated with retransmissions and breaks down. Here we define a stable ALOHA system as one that clears out the blocked packets in a finite time, and has only a finite number of blocked packets in the system, all with arbitrarily low probability. This is a necessary condition for previous definitions of stability to be meaningful. In considering waiting time, we calculate the mean and other moments of the waiting time of a terminal when it enters the system to find (n - 1) other terminals already there competing for the channel. Under this control, the average time is proportional ton. Two things should be pointed out. The first is that the control requires exact knowledge of the number of terminals contending for the channel, and hence is not implementable, except as an approximation. The second is that the analysis takes into account the dynamic comings and goings of terminals.

A new class of generalized stack algorithms for decoding convolutional codes is presented. It is based on the Zigangirov-Jelinek (Z-J) algorithm but, instead of extending just the top node of the stack at all times, a number of the most likely paths are simultaneously extended. This number of paths may be constant or may be varied to match the current decoding effort with the prevalent noise conditions of the channel. Moreover, the trellis structure of the convolutional code is used by recognizing and exploiting the reconvergence of the paths. As a result the variability of the computation can be reduced up to a limit set by the "ideal" stack algorithm. Although the tail of the computational distribution is still Pareto, it is shown and verified from simulation with short constraint length codes(K \leq 9)of rate\frac{1}{2}that, compared to sequential decoding, the variability of the number of computations per decoded bit and the maximum computational effort are both reduced at the cost of a modest increase in the average decoding effort. Moreover, some of the error events of sequential decoding are corrected. These algorithms fill the gap between the one-path sequential decoding nad the all-path Viterbi decoding.

This paper is concerned with the problem of designing a minimum-cost network of acceptable performance that connects several remote terminals to a central processor using multidrop lines. It is assumed that the message generation rate at each of the terminals is known and that the communication lines of the network have the same capacity. A simple model of the network is used to derive performance constraints for the design procedure. A new heuristic design procedure is proposed. This procedure is compared to other heuristic methods and is found superior in some cases. An improved version of the branch-and-bound (BB) algorithm of Chandy and Russell is developed and tested.

Sullivan's recent extension of Gallager's time diversity encoding scheme for combating bursts when there are errors in the guard space is based on the concept of one convolutional code that is contained in another. This paper shows that Sullivan's necessary and sufficient conditions for containment imply a simple factorization of the contained code. Implications for code design, encoders, and decoders for burst- and random-error channels are noted.

This paper shows the existence (by construction) of rate\frac{1}{2}convolutional codes that correct bursts of lengthBortrandom errors. The codes have memory length and guard space requirements that are asymptotically4Band minimal effective length. Kohlenberg introduced the term "diffuse code" for his two random-error or single-burst error-correcting codes with minimal effective length and both a memory and guard-space requirement of3B + 1. To this point, there does not seem to be any procedure for finding codes with minimal effective length and guard space requirements asymptotically3B.

Turin [1] has studied the problem of optimal sequential detection over a channel with feedback when the signals used are subject to peak and average power constraints. With special additional constraints on the signals he was able to obtain a series solution for the first passage probability density and hence find optimal signals when the ratio of peak power to average power was infinity or one. Horstein,[2] concurrently with this study, was able to find optimal signals for arbitrary ratios of peak to average power when the signals were subject to the same special constraints. This paper presents a simpler and more direct approach for obtaining optimal signals which minimize the expected time to decision for arbitrary peak power constraints and various average power constraints. Explicit closed form solutions are derived for the expected energies and times to decision without having to first obtain the probability distribution of the first passage time. No special constraints are required on the signals. For communication with white noise in the feedback link, optimal stationary signals are found for peak and average power constraints. It is shown that communication rates up to but strictly less than channel capacity are possible with noisy feedback. However, it is also noted that for the schemes considered here, the stationary signals and white noise in the feedback link imply infinite feedback power.