On Distributed Communications Series

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

III. Description of the Program: Subroutines

The program consists of a set of subroutines written in FORTRAN. As the program was constantly changed, certain parts of the program listing in the Appendix are residuals from earlier runs.[1]

MAIN

MAIN reads the input and calls up most of the subroutines in the basic program.

SETTAB

SETTAB is used at the beginning of each run to establish an initial maximum handover number table for each link of each node. The handover number from each node to every other node via all possible links is set to the value KMAX, which is simply a starting value. The border links of the network are set to IFIN (32,000) to keep messages within the chosen size network.

RANTIM

RANTIM sets values of random-length time delays. It has changed since the first draft of the program, when it was thought necessary to maintain separate values for switching delays in the nodes and in the links. However, as it now seems possible to build hardware to switch all messages within an almost constant time interval (see ODC-VII), we have chosen to combine these delays into a single "pipe filling" and message-length combination delay. As real-world networks have varying-length paths, each separate transmission delay is chosen by use of a random number generator test per network run. As each link in the system can send and receive simultaneously (full duplex), this subroutine sets the delay time on both legs of each link to the same value.

MOVE

MOVE is the heart of the program. It contains an iterative FORTRAN "DO" loop to manage all of the message propagation actions of the system. Snapshot printouts which indicate network status behavior are performed within this subroutine. Each message in the network is tested to determine its location and whether sufficient propagation time has elapsed to change its status. If, at the time of examination, the message is at a node and is free to move to an output link, subroutine SELINK (see below) is called. Similarly, if the message is traveling down a link and exceeds the propagation time delay, SELNOD (see below) is called into play.

NEW

Subroutine NEW is used to generate messages. If the message has either reached its desired terminal destination, or its maximum allowable handover number has been exceeded, subroutine NEW is called to generate a new inessage. Since we are simulating an array of 49 stations, it was convenient to make the "from" address of a message exactly equal to the number of the message modulo 49. (This explains why the number of messages in the system at any one time in most of the runs is a multiple of 49.) The "to" address of each message is chosen at random. For example, when a message from Node 3 has been delivered, another message will start from Node 3. One set of trial runs was made with all messages starting from a central node, while all other runs generated traffic uniformly at all nodes.

SELINK

SELINK selects the link or path to be taken to convey each message through the network. Each link is tested to see if it is usable. The output link chosen is that link which is not busy and which has the lowest-value entry on the local handover number table.

SELNOD

Subroutine SELNOD serves two purposes. It checks to see if messages have arrived at end destinations, and it updates the learning table. Subroutine SELNOD checks the handover number and the destination of the message. If either the maximum allowable handover number has been exceeded or the desired end destination has been reached, a signal is set to call subroutine NEW; otherwise, the handover number is merely increased by one. Next, the lowest previously-found entry in the handover table is compared to that of the handover number of the newly arrived message. Whichever is smaller replaces the former value on the handover table. This permits the node to determine the best directions for sending future traffic. This minimum-value substitution is called "perfect learning," as it provides a record of the shortest path a message ever took to arrive at the node. In order to make the network insensitive to possible errors and to allow for rapid change of routing, "imperfect learning" is used. Imperfect learning includes weighting factors to allow for error, failure of the network, and repair of the network.

PRINT and ERROR

These routines control the various forms of printouts needed to evaluate network performance.

DAMAGE

Subroutine DAMAGE is used to destroy nodes in order to simulate failure or damage effects. The basic DAMAGE subroutine can destroy nodes in a controlled random fashion where the percentage of nodes to be destroyed has been specified.


[1] This section presumes familiarity with FORTRAN. The reader who is not soconversant may wish to advance directly to Sec. IV, p. 11.


Contents
Previous chapter
Next chapter