Streaming content distribution networks with minimum delivery cost

A Content Distribution Network, or CDN, is a system to improve the delivery of content to the end users (or clients) in the Internet, in which popular content may be cached or replicated at a number of servers, placed closer to some of the client populations. The design of a CDN consists of defining: (a) which content should be replicated at each server (server content), (b) the number of servers and where they should be placed in the network (server placement), (c) which server a client's requests should be sent to (server selection) and (d) how the server responses should be routed to the clients (routing). CDNs were originally designed for traditional web files (i.e., HTML, image files). However, given the increase in streaming media (i.e., video and audio) content in the Internet, the development of efficient CDN design methods that take into account the special characteristics of media objects is of great interest. These characteristics include the sustained high bandwidth requirements and the new and complex tradeoffs introduced by multicast delivery.; The main goal of this thesis is to develop methods for designing streaming media CDNs with (near) minimum delivery cost, where the delivery cost includes both the server and the network bandwidth costs. We propose and evaluate a new simple minimum cost caching algorithm for conventional CDNs that use unicast delivery. We also develop cost models to determine the optimal server content, server placement and routing for scalable CDNs that use multicast delivery, and new approximate algorithms for determining the near optimal server placement and routing for scalable CDNs. In order to develop the cost models and to evaluate our solutions, a reasonably small set of system and workload parameters that have primary impact on a CDN delivery cost are identified. These parameters are varied over a wide range of values in order to cover as much of CDN design space as it is practically feasible. This thesis also provides an extensive analysis of the workloads of two educational media servers to provide data for creating realistic synthetic workloads and to gain insights into efficient CDN design strategies.