Minimizing delivery cost in scalable streaming content distribution systems

Recent scalable multicast streaming protocols for on-demand delivery of media content offer the promise of greatly reduced server and network bandwidth. However, a key unresolved issue is how to design scalable content distribution systems that place replica servers closer to various client populations and route client requests and response streams so as to minimize the total server and network delivery cost. This issue is significantly more complex than the design of distribution systems for traditional Web files or unicast on-demand streaming, for two reasons. First, closest server and shortest path routing does not minimize network bandwidth usage; instead, the optimal routing of client requests and server multicasts is complex and interdependent. Second, the server bandwidth usage increases with the number of replicas. Nevertheless, this paper shows that the complex replica placement and routing optimization problem, in its essential form, can be expressed fairly simply, and can be solved for example client populations and realistic network topologies. The solutions show that the optimal scalable system can differ significantly from the optimal system for conventional delivery. Furthermore, simple canonical networks are analyzed to develop insights into effective heuristics for near-optimal placement and routing. The proposed new heuristics can be used for designing large and heterogeneous systems that are of practical interest. For a number of example networks, the best heuristics produce systems with total delivery cost that is within 16% of optimality.

I. Introduction

Recent SCALABLE streaming protocols for on-demand delivery of popular media content promise significant server and network bandwidth savings (e.g., [6], [10], [13], [14]). However, a key unresolved issue is how to design scalable streaming content delivery systems. This problem involves placing replicas of popular objects closer to some of the client sites so as to reduce content delivery cost. The key questions are how many replicas, where each replica should be placed, where to route client requests, and how to route the streams that the clients receive. The goal considered in this paper is to minimize total delivery cost, which in general includes both total network and total server delivery cost. Once the replicas are placed for minimum delivery cost, packet-loss recovery can be provided by using techniques such as those described in [4] or [18], while client latency can be minimized by storing a small prefix closer to the clients.