代理伺服器之快取策略於影音串流系統之應用

Proxy Caching Strategies for Streaming Video Applications

詹振隆(Chen-Lung Chan)

指導教授 ： 王家祥

國立清華大學/電機資訊學院/資訊工程學系/博士(2006年)

摘要

在隨選視訊系統（VOD）中，我們常會在代理伺服器（Proxy）上實做 Prefix Caching 或 Interval Caching 這兩種快取策略，來同時提高系統效能與使用者播放滿意度。然而，這兩種策略都是為了服務同質性的使用者而設計，在面對現實系統中常存在的異質性用戶（具有不同的網路頻寬或記憶體緩衝空間）時，表現則不盡理想。本論文探討異質性之用戶端緩衝空間所造成的問題，並且介紹了兩個用來提升系統效能的機制。第一個機制是一個可最小化各 Proxy 頻寬用量的快取策略。在此，我們分析了 Prefix Caching 與 Interval Caching 的理論效能，並且定義了這些策略對系統效能的改善量。根據這些分析結果，我們設計了一個混和的快取策略，在 Proxy 上同時使用 Prefix Caching 與 Interval Caching 來減少頻寬使用；同時，我們也提供一個最佳的快取空間分配演算法，來決定所要使用的快取類型與大小。我們所提出的另一個機制就是讓各 Proxy 能互助合作，從而提供一個多點傳輸服務，並命名為 Buffer-Assisted On-Demand Multicast。在我們所設計的 Multicast 服務中，位於相同 Multicast Group 的使用者仍能夠在不同的時間存取該 Multicast Stream，因此能更進一步減少伺服器的負載。我們證明了要為使用者找出最佳傳輸路徑和緩衝空間分配是一個 NP-Complete 的問題，也針對完整連接的疊蓋式網路設計了一個最佳化 Routing 演算法，並針對一般架構的網路設計了一個 Heuristic 演算法。透過一些模擬實驗即可驗證，上述的兩個機制都能明顯減少 VOD 系統之伺服器負載與網路頻寬用量。

關鍵字

代理伺服器 ； 快取 ； 影音串流

並列摘要

Proxy caching strategies, especially prefix caching and interval caching, are commonly used in video-on-demand (VOD) systems to improve both system performance and the playback experience of users. However, because these caching strategies are designed for homogeneous clients, they do not perform well in the real world where clients are heterogeneous (i.e., different available network bandwidths and different sizes of client-side buffers). This thesis investigates the problems caused by heterogeneous client-side buffers and proposes two mechanisms for performance optimization. The first mechanism is a caching strategy for minimizing the input bandwidth of individual proxy while serving heterogeneous clients. We analyze the theoretical performance of prefix caching and interval caching, and then derive cost functions to formulate the corresponding performance gains. Based on these analytical results, we propose a hybrid caching strategy that employs both prefix caching and interval caching to minimize the input bandwidth of a proxy. An optimal cache allocation algorithm is also presented to determine the best ratio of prefix caches and interval caches in a proxy. The other mechanism we proposed is cooperating proxies to construct an overlay multicast infrastructure, called Buffer-Assisted On-Demand Multicast (BAODM). In BAODM, the receivers in a multicast group can access the multicast stream asynchronously, so the server load of a VOD system can be further reduced. We prove that the time complexity to determine an optimal routing path and the corresponding buffer allocations for each request over general graph networks is NP-complete. Besides, we propose an optimal routing algorithm for fully-connected overlay networks and a heuristic routing algorithm for general graph networks, respectively. Through the simulation results, both mechanisms show that they can significantly reduce both the server load and the network bandwidth consumption of a proxy-assisted VOD system.

並列關鍵字

Proxy ； Caching ； Streaming Video

參考文獻

[1] N.L.S. da Fonseca and R.D.A. Facanha, “The Look-Ahead-Maximize-Batch Batching Policy,” IEEE Trans. Multimedia, vol. 4, no. 1, Mar. 2002, pp. 114–120.

[2] S.-H. G. Chan and F. Tobagi, “Tradeoff Between System Profit and User Delay/Loss in Providing Near Video-on-Demand Service,” IEEE Trans. Circuits and Systems for Video Technology, vol. 11, no. 8, Aug. 2001, pp. 916–927.

[3] W.-E. Poon, K.-T. Lo, and J. Feng, “Adaptive Batching Scheme for Multicast Video-on-Demand Systems,” IEEE Trans. Broadcasting, vol. 47, no. 1, Mar. 2001, pp. 66–70.

[4] S. Viswanathan and T. Imielinski, “Metropolitan Area Video-on-Demand Service Using Pyramid Broadcasting,” Multimedia Systems, vol. 4, no. 4, Aug. 1996, pp. 197–208.

[5] C.C. Aggarwal, J.L. Wolf, and P.S. Yu, “A Permutation-Based Pyramid Broadcasting Scheme for Video-on-Demand Systems,” in Proc. IEEE Int. Conf. Multimedia Computing and Systems, Jun. 1996, pp. 118–126.