On Distributed Communications Series

II. Digital Simulation of Hot-Potato Routing in a Broadband Distributed Communications Network


The small-memory, stochastic, hot-potato routing scheme described in Vol. I in this series has been simulated on the IBM 7090 computer, using FORTRAN language. The simulation has shown that an efficient store-and-forward routing doctrine can be performed in a distributed network using a relatively simple policy at each Switching Node.

The computer program simulated real-time operation of the network, with a time factor of about 540 seconds of computer time to one second of real-time operation. Network learning time was determined as a function of traffic volume, redundancy of connection, and maximum allowable handover number. It was found that, from a dead start, a 49-node network can learn to route messages very effectively within about one second of scaled real-world time. The traffic-handling capacity of the network was examined, and it was found that loadings on the order of about 50 per cent of peak capacity were possible without excessively increasing the transmission path length or delay time.

The mean handover number (path length) for messages traveling through the network was studied as a function of maximum allowable handover number and of redundancy. It was found that the mean handover number is quite insensitive to maximum allowable handover number; and, the greater the link redundancy, the lower the mean handover number.

During the simulation it was found that a certain percentage of the messages were dropped when the handover number exceeded the allowable maximum. This problem has been solved by J. W. Smith and is described in Vol. III which is a continuation of the work started in the present Memorandum. With this exception, no major difficulties were encountered. It appears that the basic routing doctrine examined can permit a network to suffer a large number of breaks, then quickly reconstitute itself by rapidly relearning to make "optimum" use of the surviving links.