Stochastic traffic processes are open nonstationary (dynamic, transient), yet naive assumptions about stationarity lead to unrealistic forecasts. Format tests for stationarity are impractical in real time, and some heuristic tests are imprecise. Lagged autocorrelations are used in time series analysis for empirical stationarity tests, model identification and forecasting, but traditional methods are too slow for sub-second computation of empirical autocorrelation functions. We describe a mechanism for computing the empirical lag autocorrelation function of time series {X/sub i/} in real time, and for using this function to detect nonstationarity conditions. Fuzzy logic is used to design a fast and accurate neural classifier of stationarity, The classifier's estimate is updated with each new observation. No passes through sample datasets are necessary, and there is no need to overly compensate for round-off error. A real-time classifier of stationarity is fundamental to any sub-second traffic forecasting mechanism.

A tandem queue model is developed that models the end-to-end delay behavior in networks that employ sliding window flow control. Messages arriving to find the window filled are assumed to be queued outside the network to await their turn to enter. The model is analyzed using a hierarchical decomposition method; the key step entails incorporating the fact that the interdeparture process is not exponentially distributed. End-to-end delay in virtual circuits can then be obtained by modelling a virtual route as a tandem queue [1] using the method of “adjusted rates.”

By classifying traffic conditions into four categories, we investigate the preference for a deterministic or an adaptive routing strategy with respect to a traffic category. The four categories are: 1) balanced, emulating known and stationary traffic conditions; 2) balanced with surge, emulating a balanced traffic condition with possible unexpected sudden increases in traffic demands between some source-destination pairs; 3) unbalanced, emulating unknown or nonstationary traffic conditions with low to moderate traffic loading; and 4) chaotic, emulating unknown or nonstationary traffic conditions with heavy traffic loading. Our study concludes that a well-chosen deterministic strategy is better for balanced traffic; both deterministic and adaptive procedures are appropriate for balanced traffic with surge; and a well-chosen adaptive strategy is preferred for the unbalanced and chaotic conditions. We also attempt to define a routing strategy that behaves almost deterministically when appropriate and adaptively otherwise. We contend that an adaptive routing strategy with a second-order metric1 + a_{1}Q + a_{2}Q^{2}, where1 \gg a_{1} \gg a_{2}are constants andQis the queue size at a link, is a good compromise. (Values of a1and a2depend on network topology and congestion control strategies.) Our reasoning and results are supported and verified by experimenting with a detailed simulation program.

With the double-digit rate of increase in the cost of energy, transportation and personnel and the double-digit rate of decrease in the cost of computing and communications, the demand to bring remote information to users via data networks for cost savings and convenience is overwhelming.

In this concise paper we described the simulation approach for a general centralized computer communication system with emphasis on efficiency and versatility. The simulation program consists of three modules representing different levels in a hierarchy. The lowest level models the polled multidrop line connecting remote terminals to the concentrator. The second level models the trunk lines and the concentrator which interfaces the multidrop lines of lower speed to one or more higher speed trunk lines connected to a central computer. The highest level models the central computer which communicates with remote terminals via the trunks. A hybrid simulation approach is used to ease program development and to shorten computer running time. When feasible, empirical distributions, analytical formulas, or analytical models are used to eliminate simulation steps and simplify simulation procedures. The techniques developed are illustrated by application to the NASDAQ system.

Abstract The ARPA Computer Network, which today links over 60 host computers in more than 40 different locations is a significant advance both in computer systems and data communications. The ARPANET uses a communication technique called packet switching to dynamically select message routes through the network. In this paper, we discuss a number of important properties of the network as well as the techniques used to identify these properties. Among the topics discussed are ARPANET growth, performance sensitivity to traffic variations, incremental costs for adding capacity and new sites, peak throughput costs, and network reliability.

The problem of designing minimum-cost multidrop lines which connect remote terminals to a concentrator or a central data-processing computer is studied. In some cases, optimal solutions can be obtained by using either linear integer programming or a branch-bound method. These approaches are not practical, since they lack flexibility and require an enormous amount of computer time for most practical problems. As a consequence, heuristic algorithms have been developed by various authors. In this paper, we point out that all of these algorithms fall into the class of minimum spanning tree (MST) problems, constrained by traffic or response time requirements. The difference between them is mainly the sequential order with which a branch or a line is selected into the tree. Without the constraints, all algorithms converge to a MST. With the constraints, they form different subtrees. Most of the algorithms can be unified into a modified Kruskal's MST algorithm. In the modified algorithm, a weight is associated with each terminal. Let wibe the weight associated with terminali, andd_{i}{j}be the cost for the line directed from terminalito terminalj. When the algorithm fetches the cost for the line, it replaces it withd_{i}{j} - w_{i}. In some cases, wi's need to be readjusted in the middle of the algorithm. The difference between all existing heuristic algorithms is in the way wi's are defined. If wiis zero for alli, the algorithm reduces to the unmodified Kruskal's algorithm; if wiis set to zero whenever a line incident to terminaliis selected as a tree branch, the algorithm reduces to Prim's MST algorithm. An extension of the algorithm to the solution of an associated problem of partitioning the terminals with respect to a predetermined set of concentrators, multiplexers, terminal interface processors, or central computers is also derived. The efficiency of an algorithm depends greatly on how it is implemented. The computational complexity of the unified algorithm is in the order ofN^{2} log Nfor the most general case, whereNis the number of terminals. By using good heuristics, it reduces toK_{1}N log N + K_{2}N, where K1and K2are constants, for many practical applications. The algorithm has been applied to large networks with over 1000 terminals, yielding excellent results and using only 15 seconds of computer time on a CDC 6600 computer. Designs obtained by using different wi's are compared.

Abstract The problem of routing flow in a network of computers is extremely complex. This is especially formidable when routing is to be incorporated in iterative analysis and design. Among the properties of desirable flow patterns is low average delay from message inception to arrival. In this paper, we discuss procedures for minimizing average delay subject to a set of flow constraints. Heuristic routing procedures are presented and compared to optimum routing procedures. Computational experience is given.

Abstract Major design problems for centralized computer networks are link layout and capacity assignment. The objective is to select link locations and capacities so that the average time delay required to transmit a message from any node to the central node does not exceed a specified maximum. The design problem is to find the least cost system which satisfies the time delay constraints for given levels of traffic. In this paper, we describe an algorithm to select globally optimum link capacities for specified tree structures. We also give a heuristic method for finding low cost tree structures. The methods have been programmed and are capable of handling networks with thousands of nodes. In addition, they can consider any finite set of link capacities with an arbitrary cost structure and do not depend on the mathematical model used to calculate average time delay.