This project will develop and analyze algorithms for multipoint routing in communication networks. A multipoint connection, instead of joining just two hosts by a path, joins a set of two or more hosts; and instead of a single path, a multipoint connection consists of a set of links and switches creating multiple paths, usually in the form of a tree. The underlying model used here is a connection oriented communication network represented by an undirected graph with edge costs. In addition, bandwidth is reserved for each connection, so that communication delay is not the main consideration, but, instead, the main criteria for route selection is the minimal usage of network resources. Finally, since a practical multipoint routing algorithm must be able to deal with a set of hosts that changes over time, the dynamic Steiner tree problem is the appropriate graph theoretic model for this problem. This investigation will include empirical studies of routing algorithms through the use of a routing simulator along with the more theoretical analysis. The primary objective is to develop more efficient multipoint routing algorithms that will allow future networks to effectively support a wide range of applications such as conference calls and video broadcasts.
