Overlay multicast is a new communication paradigm in which end hosts relay data to each other via unicast connections. It offers many advantages over IP multicast, including the instant deploy-ability on the current Internet and great flexibility at supporting various distribution-based applications. In particular, one can augment the multicast throughput by exploring the route diversity of overlay networks. The fundamental question is, given a multicast session, how to achieve its optimal throughput subject to the network capacity constraint.

In this talk, I will present our study on this problem via theoretical modeling, algorithm design, and system deployment. By formulating this problem using the multi-commodity flow theory, I show that although the same problem is NP-hard in the case of IP multicast, it is solvable in polynomial time in overlay networks. Based on this finding, an optimal flow routing algorithm is proposed for overlay multicast. The algorithm is further adapted as we add to the basic problem new constraints, such as maintaining fairness among competing multicast sessions, limiting the number of overlay trees per session, etc. The adapted algorithm is proved to be either optimal, or achieving the best approximation bound among existing solutions. At the end of this talk, I will discuss the development of applications which implement our algorithms, e.g., layered peer-to-peer streaming.

Yi Cui received his B.S. degree in 1997, and M.S. degree in 1999, both from the Department of Computer Science at Tsinghua University. Currently he is a PhD candidate in the Department of Computer Science at University of Illinois at Urbana-Champaign. His research interest includes networking and distributed systems with a focus on overlay network, peer-to-peer system, multimedia system, ubiquitous computing, and wireless network. Yi's homepage can be found here.