The greedy, the naive, and the optimal multicast routing, from theory to Internet protocols

grantor: University of TorontoThis work studies the problem of multicast routing both at a theoretical and a practical level. Multicasting involves the distribution of the same data to several receivers at the same time. Efficient multicast routing can reduce the communications cost of the distribution tree. In this document, we extend and study the most widely used routing algorithms in a variety of problems, and we compare their performance theoretically and through simulations. First, we study how the asymmetry of directed networks and the membership behavior affect the performance of these algorithms. We prove bounds for the various cases of these problems in a worst case analysis. Second, we propose algorithms for multicast connections where the users have different quality expectations from the multicast connection. We prove bounds for the performance of our algorithms, and examine their performance in a variety of scenarios through simulations. Third, we propose, QoSMIC, a multicast protocol for the Internet. A major advantage of QoSMIC is that the routing decisions consider the quality requirements of the users. In addition, the protocol limits the role of pre-configuration decisions, which cause problems in the employment of some previous protocols. Another important feature of the protocol is its flexibility; it can scale to large networks, and it can adapt and evolve with the needs of the applications and the requirements of the users.Ph.D