A cost-effective structure for a large network is a multilevel hierarchy consisting of a backbone network and a family of local access networks. The backbone network is generally a distributed network, while the local access networks are typically centralized systems. In special cases, the network may consist primarily of either centralized or distributed portions. This paper discusses topological design problems for such systems, including the concentrator location problem, the terminal assignment problem, the terminal layout problem (the constrained minimum spanning tree problem), the distributed network topological layout problem, and the backbone node location problem. Recent algorithm research, including exact and heuristic problem solutions, are described and computational experience is given. Finally, open problems in large-scale topological design are reported.

Packet-switching broadcast radio networks are receiving considerable attention as a feasible solution for applications involving fast network deployment requirements, inaccessible physical environments, and mobile communication devices. Such networks also offer economic alternatives to traditional multiplexing schemes for local distribution. Most of the published papers relating to packet-switching broadcast radio networks address the case in which all communication devices are within an effective transmission range of the destination receiver, thus forming a single-hop network in which no packet routing is involved. In this paper, we address multihop networks. The problems encountered in packet transportation are identified and strategies to resolve these are proposed.

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.

This paper is the first of a two part study summarizing the results of a research program on the survivability analysis of command and control communication(C^{3})systems. In the first part, we consider the formulation of realistic survivability models and criteria, determine the fundamental physical problems affecting survivability analysis, and determine suitable approaches to the survivability problem. The second part first discusses algorithms for deterministic analysis of C3systems to identify bottlenecks and more vulnerable elements in network structure. The problems encountered in probabilistic survivability analysis and basic probabilistic analysis techniques are then discussed. Finally, an efficient, practical probabilistic survivability analysis procedure is given and an example of its use is presented.

This paper is the second of a two-part study summarizing the results of a research program on the survivability analysis of command and control communication(C^{3})systems. In the first part, we consider the formulation of realistic survivability models and criteria and the fundamental physical problems affecting survivability analysis. In this paper, we first discuss algorithms for deterministic analysis of C3systems to identify bottlenecks and more vulnerable elements in network structure. The problems encountered in probabilistic analysis techniques are then discussed. Finally, an efficient, practical probabilistic survivability analysis procedure is given and an example of its use is presented.

Abstract The design of the ARPA Computer Network brought together many individuals with diverse backgrounds and philosophies. In this paper, we review the methods used in the design of the Network from the vantage of over two years' experience in its development. The design variables, system constraints, and performance criteria for the network are discussed along with an evaluation of the tools used to design an efficient and reliable system. The design procedures and the conclusions reached about the network's properties appear to be generally applicable to message switched networks. Consequently, the results of this paper should be useful in the design and study of other store‐and‐forward computer communication networks.

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.

Abstract This paper considers networks with randomly failing links and nodes. In Part 1, nodes are assumed to be perfectly reliable. A combinatorial analysis is given when all links have equal reliabilities. Two general simulation methods are described. The first is particularly useful if a wide range of failure probabilities is to be considered. The second combines a combinatorial analysis with stratified sampling to yield major computational savings. Later parts will describe generalizations, decomposition methods for large networks and applications to computer network analysis.

The decomposition property, a necessary condition for linearity, is defined for discrete-time systems. N-state machines with this property have finite memory μ≤N−1. Linear and autonomous systems are important classes of systems with decomposition. Several representations of systems with decomposition are given and a general form of the discrete-time state equations for a finite-memory system with decomposition is derived. An algorithm is developed by which an arbitrary complete-sequential machine may be tested for decomposition.

A major limitation for time-sharing systems is the time delay encountered in transferring records between central “fast” memory and peripheral memory devices. In this paper the transfer characteristics of disk storage devices are considered. Expected seek time and expected rotational latency are taken as measures of performance for the disk. The following aspects of disk files and their behavior are considered: the speed profile of the positioning mechanism and its effect on seek time; effects of the probability distribution of information stored on tracks; track overflow of records; dynamic queuing strategies; reduction of rotation time by buffered read techniques; and strategies for using multiple-arm devices.