IMPROVED NEURAL HEURISTICS FOR MULTICAST ROUTING

Future networks must be adequately equipped to handle multipoint commu nication in a fast and economical manner, Services requiring such supp ort include desktop video conferencing, tele-classrooms, distributed d atabase applications, etc, In networks employing the asynchronous tran sfer mode (ATM) technology, routing a multicast is achieved by constru cting a minimum cost tree that spans the source and all the destinatio ns, When the network is modeled as a weighted, undirected graph, the p roblem is that of finding a minimal Steiner tree for the graph, given a set of destinations, The problem is known to be NP-complete. Consequ ently, several heuristics exist which provide approximate solutions to the Steiner problem in networks, In this paper, we show how the rando m neural network (RNN) can be used to significantly improve the qualit y of the Steiner trees delivered by the best available heuristics whic h are the minimum spanning tree heuristic and the average distance heu ristic. We provide an empirical comparison and find that the heuristic s which are modified using the neural network yield significantly impr oved trees.