On Distributed Communications Series
II. Digital Simulation of Hot-Potato Routing in a Broadband Distributed Communications Network
The size of the network simulated was limited by the amount of storage available in the IBM 7090 computer using FORTRAN. A heavy storage requirement was dictated by the need for each simulated node or station to maintain a table of recorded handover numbers--the tag appended to each message indicating the number of times that message has been relayed. For each node, a table containing handover numbers to every other node via every one of up to a maximum of eight links is needed.
The choice of a maximum of eight links was made by limiting the simulation to networks with a redundancy level, R, of four or less, defined as follows:
Specifically, the configurations considered were for redundancy levels of 1, 1.5, 2, 3, and 4. In a large array, the number of links emerging from a node is equal to two times the redundancy level. The network under consideration was limited to a seven-by-seven array.
This simulation was written to examine and to test the properties of a network of a type which has never been built. It was hoped that the choice of such hitherto unspecified parameters as the maximum handover number and the allowable traffic volume could be narrowed. Results vary decisively as these parameters change. We sought first a reasonably good set of basic key parameters before adding additional refinements necessary to simulate a real-world system. Thus, the simulation changed in midstream as modifications were made from time to time to improve the routing doctrine. For example, while tracing a message as it moved through the system it was found that certain conditions would cause two nodes to relay messages in a ping-pong fashion. Instead of moving out into the system, the message simply bounced back and forth between the two nodes. This was straightened out by a modification to the switching rules before continuing subsequent runs.
The Routing Doctrine in the First SimulationThe initial constraints were:
- Each node accepts new traffic messages if, and only if, open storage
capacity exists at the node.
- A "from" address and a handover number tag is appended to each message
inserted into the network.
- Every time a message is relayed from one node to another, the handover
number is incremented by cne.
- A table of the "minimum" handover number encountered relative to each
originating station over each link in the network is stored at each node.
- Before the simulation is started, the entries on the tables of handover
numbers are set to predetermined maximum values.
- Messages found in the network with a handover number exceeding a maximum
allowable value are dropped. (On some runs, the location, the source, and the
desired end point of such dropped messages are output to facilitate isolation
of trouble spots.)
- Messages correctly delivered are erased. (On some runs, the handover
number, station of origin, and terminal or "sink" station are printed out for
- Messages are routed by examining the handover number table and choosing the
outgoing "non-busy" line bearing the lowest handover number table entry.
- If all lines are busy, a message waits at the node until one is free.
 A larger array of stations (> 11 x 11) has been simulated by J. W. Smith, as described in ODC-III.