A neural network method for minimum delay routing in packet-switched networks

In this paper, a neural networks (NNs) based two-phase routing algorithm is proposed. The aim of the first phase is to find a set of alternative routes for each commodity, while the traffic of each commodity is optimally distributed on the alternative routes in the second phase. Our final goal is to route all messages so that the average time delay of a message is minimized. Since the Hopfield neural network (HNN) can only solve problems whose energy functions can be expressed as quadratic forms, the expression of the average time delay of a packet needs first to be simplified and then explicitly included into the energy function. Our algorithm is applied to two network models, both of which have been previously analyzed by other researchers using mathematical methods. Compared with previous results, the proposed algorithm considerably reduces the time delay a packet encounters. A large number of experiments also indicate that the proposed algorithm has very good stability. Our work provides a possible routing policy for future high-speed communication networks due to the fact that a hardware-implemented NN can achieve an extremely high response speed. (C) 2001 Elsevier Science B.V. All rights reserved.