On Distributed Communications Series

III. Determination of Path-Lengths in a Distributed Network


This Memorandum is one in a series of eleven RAND Memoranda detailing the Distributed Adaptive Message Block Network, a proposed digital data communications system based on a distributed network concept, as presented in Vol. I in the series.[1] Various other items in the series deal with specific features of the concept, results of experimental modelings, engineering design considerations, and background and future implications.

The series, entitled On Distributed Communications, is a part of The RAND Corporation's continuing program of research under U.S. Air Force Project RAND, and is related to research in the field of command and control and in governmental and military planning and policy making.

The present Memorandum, the third in the series, is a continuation of the model simulation study reported in the previous volume. Since a network of the type proposed had never been built, there was much we did not know about its performance. For example, we wanted to learn more about the distribution of message path-lengths in the network, in order that transmission times might be determined; we wanted to know how the network behaved under heavy loading--such as would occur during a crisis; we wanted to know how the network would react when a "hog" station or stations attempted to purposely overload the network; we wanted to know how many message blocks would be lost if a policy of dropping traffic that has circulated longer than some specified time were used.

Because of the complexity of such networks, our only high-confidence tool for predicting performance was the Monte Carlo simulation, wherein messages are created and circulated in a computer model of the network, statistics of traffic-flow are examined, network parameters are changed, and the network is re-examined.

A FORTRAN simulation (for the IBM 7090 computer) was described in Vol. II in the series, together with the results of the simulation performed. There were three shortcomings to this effort: first, the size network that could be accommodated was smaller than desired; second, an undue number of messages was being lost during heavy overload conditions when messages began to take circuitous routes; and third, when the routing doctrine was improved to prevent such message losses, it became economically unfeasible to run the computer simulation long enough to determine the number of messages which could be expected to be lost. A target of less than one lost message per 100,000,000 was sought; this extreme requirement was selected because it was felt that future systems should be able to transmit digital data between computers--and computers are often intolerant of errors.

A new simulator, designed to resolve these problems, was encoded in the SCAT language.[2] This Memorandum describes that simulator and its appurtenances, and reports on the successful rectification of the previous effort's shortcomings. In addition, some analytical investigations of traffic-flow are described and evaluated.

[1] A list of all items in the series is found at the end of the Memorandum.

[2] International Business Machines Corporation, SHARE SOS Reference Manual--SHARE Operating System for the IBM 709, IBM Applied Programming Publication, New York, 1960-6l.