On Distributed Communications Series
II. Digital Simulation of Hot-Potato Routing in a Broadband Distributed Communications Network
V. Determination of Learning Time
We define "learning" as the utilization of knowledge acquired by each node of the system as to the network status so as to best determine the link that lies on the shortest route to each end station. If messages are routed over paths whose mean lengths approach the shortest possible path lengths, we say the network has "learned" well." A useful metric for evaluating learning is the total value of all entries in the handover number tables of all nodes. This value is called the "table total": the lower the value, the better the learning. This learning curve approaches a theoretical minimum with network use.
The network learns quickly as the volume of traffic inserted into the virgin network is increased and levels off as the capacity of the system is approached. It can be seen in Fig. 1 that starting off a new network with dummy traffic is desirable if the absolute shortest learning time is desired; otherwise, many links that may lie on short paths would never be tested.
In Fig. 1, the maximum allowable handover number was set at 40, and the number of messages per unit time was varied. With a small volume of message traffic initially, the system took longer to learn, as expected.
In Fig. 2 it can be seen that the number of messages delivered per unit time increased with network load, but leveled off at 60 per cent capacity, providing an upper bound for system load-carrying capacity under the assumed loading conditions. The mean handover number increased as the number of messages processed per unit time increased. Figure 2 shows that the average path length did not increase sharply, even up to 50 per cent loading.
The definition of the term "capacity" as used here refers to a comparison of the number of messages in the system times 100 divided by the number of links.
The rate of initial learning improved as the redundancy of the network was increased. Keeping other factors constant, twice as many messages could be delivered per unit time for a network of redundancy level 4, as for one with R = 1.5. The slopes of Fig. 3 indicate the overall learning rate.
From a preliminary examination of the learning power relative to the location of a node, it appears that the nodes on the border do the best (see Fig. 4). These nodes have fewer links to "educate." The most centralized nodes do next best, as they have the most traffic. The intermediate zone between these groups showed the poorest initial learning rate.
The Learning Rate Constant
The formula for learning or modifying the handover number table was chosen to be at+l = at + K(bt-at), where a is the handover value in the table, b is the handover number of the newly delivered message, and K is a constant. The choice of learning function was partially based upon the requrement that in the real-world it should be capable of being implemented by simple circuitry. Figure 5 shows the effect of varying the learning constant, K = 0.6, 0.8, and 1.0. The initial value of table total was the same in the three cases.