Year

2005

Degree Name

Doctor of Philosophy (PhD)

Department

School of Electrical, Computer and Telecommunications Engineering - Faculty of Informatics

Abstract

In this thesis we propose and explore the Overlay Distribution Network (ODN) concept as an alternative, more cost effective and more flexible deployment approach for Content Distribution Networks (CDN). Currently CDNs are established by deploying a dedicated server infrastructure spanning the Internet, which is prohibitively expensive. With ODN, we propose to lease transport and server resources from server and network providers to establish an overlay network of virtual servers and connecting virtual links, which is then used to deliver content in a similar manner to traditional CDNs. Such deployment strategy is expected to be less costly and could allow content network topologies and capacities to be adjusted on-the-fly according to demand. The aim of this thesis is to address the research issues that arise as a result of this new deployment approach. One of the major issues considered is ODN provisioning, which involves topology planning, resource dimensioning and content replica placement. ODN provisioning is significantly different from and more complex than its traditional CDN counterpart due to the nature of the shared infrastructure environment. ODN provisioning would not only have a different optimization objective but also require topology planning, resource dimensioning and content replica placement problems, which are currently addressed independently, to be addressed jointly. To address this ODN provisioning challenge, we develop a provisioning framework that could be used to formulate ODN provisioning models that meet these new requirements. ODN provisioning models for a number of key content distribution applications, including web content distribution, pay-per-view content distribution and live streaming multimedia distribution, are then developed and studied. The models are formulated as mixed integer linear programming optimizations that aim to determine the optimal ODN topology, capacity and content replication pattern, which deliver satisfactory service performance at the minimum cost or maximum profit. As the above ODN provisioning models belong to the NP (Non-deterministic Polynomial) class of problems, they have extremely high complexity and cannot be solved efficiently for realistically large networks. To tackle this difficulty we develop heuristics that aim to find near optimal solutions with less computation effort. Experimental results show that our proposed heuristics are efficient and able find solutions reasonably close to the optimal (within 36% for the web ODN provisioning problem and 20% for the pay-per-view and live streaming multimedia ODN provisioning problems). Our study also demonstrates that provisioning could become significantly inefficient if the heuristics were not designed properly. For example in the web content ODN provisioning problem, a greedy heuristic adapted from existing CDN replica placement heuristics could produce ODN topologies up to 2.5 times more costly compared to a Lagrangian heuristic designed based the problem formulation structure. As part of the ODN provisioning study, we also explore the use of content clustering within the ODN provisioning process. By grouping similar content items together into clusters, which are then considered as a single item during provisioning, content clustering would help reduce provisioning complexity and allow the provisioning models to handle problems with significantly larger number of content items. We show that clustering methods previously developed for CDNs do not work well in the ODN environment. Thus we propose a new hierarchical clustering scheme, where content items are clustered based on first delivery resource requirements and then spatial demand distribution. Experimental results demonstrate that this clustering scheme has significant performance improvements over the existing ones. In this thesis we also look into the future and study the ability of the ODN to support applications that require QoS network paths among servers. To enable better support for such applications, we propose to enhance the ODN architecture with switching capabilities that allow ODN owners to control the flow of traffic within their ODN backbone. We examine and demonstrate the benefits of such capabilities using both quantitative and qualitative studies and then develop a shared switch architecture that could be used to provide such support in a shared infrastructure environment.

02Whole.pdf (1149 kB)

Share

COinS