On Distributed Communications Series

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

I. Introduction

This study examines a communications network which is comprised of an array of stations interconnected by links. A dynamically changing routing doctrine is used, such that if any paths exist between the ith station and the jth, the network will seek to route messages by the shortest such path. Such a network routing doctrine provides a very much higher degree of alternate routing capability than other networks now in use.

As it is difficult to visualize in a straightforward analysis how such networks behave, we have resorted to a "Monte Carlo" simulation. Hypothetical messages are "generated" at many stations and "transmitted" to other stations using simple pre-arranged switching rules at each node. From time to time, parameters, such as the number of messages per unit time, are varied and the behavior of the network is observed. The approach is like that of the psychologist who regards a human being as a black box: he applies inputs and observes the outputs.

All traffic to be transmitted within the model is generated at the stations or nodes. Traffic to be transmitted is first chopped into small blocks, called Message Blocks, or simply messages. These messages are then relayed from station to station through the network with each station acting as a small "post office" connected to adjacent "post offices." Messages will eventually arrive at the desired destination. In the proposed system, the transmission time and storage time at the nodes is so short that to the user there appears to be a direct link between the originating station and the end station. In effect, a slow digital-stream of bits inserted into the ith station has been stored in a buffer until enough bits are received to form the Message Block.[1] Each Message Block is whipped into the network and transmitted over high.thspeed transmission links, to finally emerge at the jth receiving station. At the jth station, the bit-stream is reconstructed into its original slow digital-stream.

Each node starts with complete ignorance of the state of its neighbors; i.e., whether its neighbors are alive or dead, and which links exist and which do not. With the routing doctrine used, each node soon learns enough about its external environment to be able to operate independently, creating a reasonably efficient overall switching flow. The term "efficient switching" is used to describe the case where messages are transmitted over paths which approximate the shortest possible path between the transmitting and receiving stations and allow high average throughput rates.

Messages are assumed to originate uniformly in the network at the early stage of the simulation. The end-destination stations are chosen at random, but a message cannot have the same origin and destination. Delays are assumed for transmission and processing time at each node and link.

A decision is made at each node as to the best non-busy link over which each Message Block shall be relayed. "Best" is defined as the shortest measured path length from the desired end station. Rather than wait for the best link to be free, the second, third, etc., best link that is not busy (or down) is taken. If at a particular node or station, several links of the node equally fulfill this requirement, one is diosen at random. In general, the link chosen is the one that appears to be the next one on the shortest path to the end station. This path choice is determined by an information tag affixed to each message, called a handover number. Each station or node notes the handover number (number of steps) of each incoming message. It keeps track of these numbers on a handover number table, which it uses to determine which of its neighbors appears to be most directly connected with each originating station. Later, the node uses this recorded information to select the preferential link over which messages to each end station should be directed.

As links may be destroyed and' other links may be repaired, and as traffic loads vary throughout the network, it is necessary to provide some means at the node for learning and forgetting the "best" direction in which to send messages going to any destination.


[1] In practice, this would be done at a substation called the Multiplexing Station, as described in ODC-VIII. (ODC is an'abbreviation of the series title, On Distributed Communications; the number following refers to the particular volume within the series. A list of all items in the series is found on p.47).


Contents
Next chapter