Using neural networks to solve the multicast routing problem in packet radio networks

The primary function of a packet radio network is the efficient transfer of information between source and destination nodes using minimal bandwidth and end-to-end delay. Many researchers have investigated the problem of minimizing the end-to-end delay from a single source to a single destination for a variety of networks; however, very little work is reported about routing mechanisms for the common case where a particular information packet is intended to be sent to more than one destination in the network. This is known as multicasting. A simplified version of the problem is to ignore the packet delay at each node, then the problem becomes one of finding solutions which require the least number of transmissions. Determination of an optimal solution is NP-complete meaning that suboptimal solutions are frequently tolerated. The problem becomes more rigorous if packet delays are included in the network topology. This paper describes a practical technique for the computation of optimum or near optimum solutions to the multicasting problem with and without packet delay. The method is based on the Hopfield neural network and experiment has shown this method to yield near optimal solutions while requiring a minimum of CPU time.