| In this work we develop new models and scalable algorithms for finding near-optimal overlay multicast routing subject to bandwidth constraints. In overlay networks each end node is connected to the underlying physical network via a channel of finite bandwidth, which may limit the number of simultaneous outgoing transmissions for the node. This limitation gives rise to a family of difficult optimization problems concerned with constructing spanning trees which satisfy degree constraints at the nodes. We consider two different optimization objectives: maximum throughput and minimum longest delay. In the delay minimization case we show that under Euclidean distances assumption the problem can be solved approximately within a constant factor of optimal, and for points distributed uniformly within a convex region our algorithm produces asymptotically optimal solution. We develop a constant factor approximation algorithm for the throughput maximization problem. Our experiments show that this problem is too complex to be solved exactly by commercially available optimization software, and therefore we develop a method for obtaining exact solution numerically using cutting planes. Finally, we analyze an example, a publish-subscribe system, and describe a method for implementing content-based subscriptions using a limed number of multicast groups. We evaluate our algorithms via numerical experiments. |
