Efficient and scalable provisioning of always-on multicast streaming services

Abstract

There is a growing need for large-scale distribution of realtime multicast data such as Internet TV channels and scientific and financial data. Internet Service Providers (ISPs) face an urgent challenge in supporting these services; they need to design multicast routing paths that are reliable, cost-effective, and scalable. To meet the realtime constraint. the routing paths need to be robust against a single IP router or link failure, as well as multiple such failures due to sharing fiber spans (SRLGs). Several algorithms have been proposed to solve this problem in the past. However, they are not suitable for today's large networks, because either they do not find a feasible solution at all or if they do, they take a significant amount of time to arrive at high-quality solutions. In this paper, we present a new Integer Linear Programming (ILP) model for designing a cost-effective and robust multicast infrastructure. Our ILP model is extremely efficient and can be extended to produce quality-guaranteed network paths. We develop two heuristic algorithms for solving the ILP. Our algorithms can guarantee to find high-quality, feasible solutions even for very large networks. We evaluate the proposed algorithms using topologies of four operational backbones and demonstrate their scalability. We also compare the capital expenditure of the resulting multicast designs with existing approaches. The evaluation not only confirms the efficacy of our algorithms, but also shows that they outperform existing schemes significantly. (C) 2009 Elsevier B.V. All rights reserved.