Improved neural heuristics for multicast routing
- 1 February 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 15 (2) , 147-155
- https://doi.org/10.1109/49.552065
Abstract
Future networks must be adequately equipped to handle multipoint communication in a fast and economical manner. Services requiring such support include desktop video conferencing, tele-classrooms, distributed database applications, etc. In networks employing the asynchronous transfer mode (ATM) technology, routing a multicast is achieved by constructing a minimum cost tree that spans the source and all the destinations. When the network is modeled as a weighted, undirected graph, the problem is that of finding a minimal Steiner tree for the graph, given a set of destinations. The problem is known to be NP-complete. Consequently, several heuristics exist which provide approximate solutions to the Steiner problem in networks, We show how the random neural network (RNN) can be used to significantly improve the quality of the Steiner trees delivered by the best available heuristics which are the minimum spanning tree heuristic and the average distance heuristic. We provide an empirical comparison and find that the heuristics which are modified using the neural network yield significantly improved trees.Keywords
This publication has 25 references indexed in Scilit:
- How bad is naive multicast routing?Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Dynamical random neural network approach to the traveling salesman problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Hopfield energy of the random neural networkPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Learning in the Recurrent Random Neural NetworkNeural Computation, 1993
- A practical version of Lee's multicast switch architectureIEEE Transactions on Communications, 1993
- Routing broadband multicast streamsComputer Communications, 1992
- MINIMUM GRAPH VERTEX COVERING WITH THE RANDOM NEURAL NETWORKPublished by Elsevier ,1992
- Multicast routing algorithm for nodal load balancingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Steiner's problem in graphs and its implicationsNetworks, 1971
- Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1968