Evaluation of algorithms for multipoint routing
Jonathan Turner, Bernard M. Waxman · 1989
This dissertation addresses the problem of the evaluation algorithms for routing of multipoint connections in a large scale communication network. A large part of this dissertation deals with the graph theoretic Steiner tree problem as an abstract version of multipoint routing. This dissertation also considers the actual problems of routing in a real network, including the dynamic nature of multipoint connections. Since the Steiner tree problem is scNP-complete, we consider several approximation algorithms including ones which we have developed. We investigate the performance of these algorithms using worst-case analysis, probabilistic analysis and empirical data. We prove that an approximation algorithm developed by Rayward Smith has a tight worst-case bound of 2 times optimum. We also propose a collection of algorithms which we conjecture have worst-case performance better than 2. It is still an open question whether or not any polynomial time approximation algorithm for the Steiner tree problem can have worst-case performance better than 2 if scNP $ e$ P. The other aspect of this work deals with the dynamic nature of multipoint connections and the interaction of multiple connections. We propose a new problem called the dynamic Steiner tree problem and present several algorithms. In addition, we prove that one that these algorithms has a worst-case bound within a factor of 2 times a best possible algorithm. The final chapter of this dissertation presents results of experiments with a simulation tool we have developed to study the performance of multipoint routing algorithms for real networks.