Host-Aware Routing in Multicast Overlay Backbone

Abstract

To support large-scale Internet-based broadcast of live streaming video efficiently in content delivery networks (CDNs), it is essential to implement a cost-effective overlay multicast mechanism by exploiting peer-to-peer distribution capabilities among end hosts. This way, the access bandwidth demand on CDN servers in the multicast overlay backbone can be largely reduced. Such a streaming infrastructure gives rise to an interesting host-aware routing problem (HARP). For a live streaming video broadcast event, each participating CDN server is made aware of the largest delay from it to end hosts within its service area. The problem is to optimize routing among CDN servers in the multicast overlay backbone such that the de facto maximal end-to-end latency from the origin server to all end hosts is minimized subject to access bandwidth constraints on CDN servers. In this paper, we frame HARP as a constrained spanning tree problem which is shown to be NP-hard. We present a distributed algorithm for HARP. Simulation experiments confirm that our proposed algorithm converges to good quality solutions that are close to the optimum.