On Distributed Communications Series

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

II. The Simulated Network

Description

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.[1]

Purpose

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 Simulation

The initial constraints were:
  1. Each node accepts new traffic messages if, and only if, open storage capacity exists at the node.

  2. A "from" address and a handover number tag is appended to each message inserted into the network.

  3. Every time a message is relayed from one node to another, the handover number is incremented by cne.

  4. A table of the "minimum" handover number encountered relative to each originating station over each link in the network is stored at each node.

  5. Before the simulation is started, the entries on the tables of handover numbers are set to predetermined maximum values.

  6. 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.)

  7. Messages correctly delivered are erased. (On some runs, the handover number, station of origin, and terminal or "sink" station are printed out for analysis.)

  8. Messages are routed by examining the handover number table and choosing the outgoing "non-busy" line bearing the lowest handover number table entry.

  9. If all lines are busy, a message waits at the node until one is free.[2]

[1] A larger array of stations (> 11 x 11) has been simulated by J. W. Smith, as described in ODC-III.

[2] This has since been changed to prevent the "alllines-busy" case from ever occurring; the procedure is called "choking," and is described in detail in ODC-III, -IV.


Contents
Previous chapter
Next chapter