A Distributed Algorithm for Overlay Backbone Multicast Routing in Content Delivery Networks

Abstract

To support large-scale live Internet broadcasting services effciently in content delivery networks (CDNs), it is essential to exploit peer-to-peer capabilities among end users. This way, the access band-width demand on CDN servers in the overlay backbone can be largely reduced. Such a streaming infrastructure gives rise to a challenging over- lay backbone multicast routing problem (OBMRP) to optimize multicast routing among CDN servers in the overlay backbone. In this paper, we take a graph theoretic approach and frame OBMRP as a constrained spanning tree problem which is shown to be NP-hard. We present a lightweight distributed algorithm for OBMRP. Simulation experiments confirm that our proposed algorithm converges to good quality solutions and requires small control overhead.