In video-on-demand (VOD) systems, it is important to minimize memory requirements and initial latency. By minimizing memory requirements, the system can support a larger number of concurrent user requests with the same amount of memory. By minimizing initial latency, the system can provide service with shorter response time. In VOD systems, as the size of the buffer allocated to user requests increases, memory requirements and initial latency increase. Hence, the buffer size must be minimized. The existing static buffer allocation scheme, however, determines the buffer size based on the assumption that the system is in the fully loaded state. Thus, when the system is in a partially loaded state, the scheme allocates a buffer larger than necessary to a user requests.
As solutions for reducing memory requirements, the memory sharing strategy and the buffer sharing strategy have been proposed in the literature. The memory sharing strategy utilizes the memory used by each user request for the other user requests. The buffer sharing strategy services multiple user requests with one buffer when they require the same video data arriving at the system within a short time interval. The buffer sharing strategy can support a larger number of concurrent user requests than is limited by the disk performance, and the memory sharing strategy can reduce memory requirement significantly for the buffer sharing strategy. Thus, we need a new scheme that uses the buffer sharing startegy combined with the memory sharing strategy to reduce the memory requirement.
In this dissertation, we propose a dynamic buffer allocation scheme that allocates to user requests buffers of the minimum size in a partially loaded state as well as in the fully loaded state. We first identify the inherent problem in the dynamic buffer allocation scheme. The problem is that the size of the buffer currently being allocated is dependent on the number of and the sizes of the buffers to be allocated in the future. To solve this problem, we represent the current buffer size as a recurrence equation to reflect its dependency on the number of and the sizes of future buffers. We provide the recurrence equation and its solution. We then propose the predict-and-enforce strategy to estimate the number of future buffers required in the recurrence equation. This strategy predicts the number of future buffers based on inertia assumptions and enforces these assumptions at runtime. Any violation of these assumptions is resolved by deferring service to the violating new user request until the assumptions are satisfied.
The dynamic buffer allocation scheme can be used with any buffer scheduling methods because it is independent of them. To demonstrate this applicability, we apply the dynamic buffer allocation scheme to three representative buffer scheduling methods: the Round-Robin (BubbleUp), Sweep*, and GSS* methods. We also formally analyze the minimum memory requirement of the dynamic buffer allocation scheme for each buffer scheduling method.
Extensive analysis and simulation show that the dynamic buffer allocation scheme reduces initial latency (averaged over the number of user requests in service from one to the maximum capacity) to $\frac{1}{29.4} ~ \frac{1}{11.0}$ of that for the static one and, by reducing the memory requirement, increases the number of concurrent user requests to 2.36 ~ 3.25 times that of the static one when averaged over the amount of system memory available.
Next, we propose the dynamic buffer sharing scheme, which is a hybrid of the buffer sharing and the memory sharing strategies. The dynamic buffer sharing scheme applies dynamic buffer allocation, which uses the memory sharing strategy, to the existing SMDP buffer sharing algorithm. The dynamic buffer sharing scheme can reduce memory requirements significantly compared with the SMDP algorithm. In addition, by using dynamic buffer allocation, this scheme solves the problem of SMDP that a buffer in service can become empty due to lack of taking the newly arriving user requests into account in determining the buffer size. Through simulation, we show that the dynamic buffer sharing scheme reduces memory requirements to $\frac{1}{3.89} ~ \frac{1}{3.27}$ of that for the SMDP algorithm.
Overall, the results that we have obtained demonstrate that the dynamic buffer allocation scheme and the dynamic buffer sharing scheme significantly improve the performance and capacity of VOD systems.
주문형 비디오 시스템에서는 메모리 요구량과 초기대기시간을 최소화하는 것이 중요하다. 이는 메모리 요구량의 최소화를 통해 동일한 메모리량으로 더 많은 사용자 요청들을 지원할 수 있고, 초기대기시간의 최소화를 통해 사용자에게 짧은 응답 시간의 서비스를 제공할 수 있기 때문이다. 주문형 비디오 시스템에서는 사용자 요청에게 할당된 버퍼의 크기가 증가함에 따라 초기대기시간과 메모리 요구량이 증가하기 때문에 버퍼 크기를 최소화해야 한다. 그러나, 기존의 정적 버퍼 할당 기법은 시스템이 완전 부하 상태임을 가정하고 버퍼 크기를 결정하여, 시스템이 불완전 부하 상태인 경우에는 사용자 요청에게 필요이상으로 큰 버퍼를 할당한다.
기존 연구에서는 메모리 요구량을 줄이기 위해 메모리 공유 전략과 버퍼 공유 전략이 제안되었다. 메모리 공유 전략은 각 버퍼에 할당되어 이미 사용된 메모리를 다른 버퍼 할당에 사용하는 전략이다. 버퍼 공유 전략은 동일한 비디오에 대한 요청들이 짧은 시간 간격으로 시스템에 도착하는 경우에 시스템이 이들 요청을 하나의 버퍼로 서비스하는 전략이다. 버퍼 공유 전략은 디스크에 의한 한계치보다 더 많은 사용자 요청들을 서비스할 수 있다. 반면에, 메모리 공유 전략은 메모리 공유를 통해 버퍼 공유 전략에 비해 메모리 요구량을 현저히 감소시킨다. 따라서, 메모리 공유 전략에 기반하여 적은 메모리 요구량으로 버퍼 공유 전략을 사용할 수 있는 기법에 관한 연구가 필요하다.
본 논문에서는 먼저 시스템의 완전 부하 상태 뿐만 아니라 불완전 부하 상태에서도 사용자 요청에게 최소 크기의 버퍼를 할당하는 동적 버퍼 할당 기법을 제안한다. 이를 위해, 우선 동적 버퍼 할당 기법에서 해결해야 할 근본적인 문제점이 현재 할당할 버퍼의 크기가 미래에 할당될 버퍼들의 수와 크기에 의존함에 있음을 규명한다. 그리고, 이 문제점을 해결하기 위해 미래의 버퍼 크기와 수를 반영하여 현재의 버퍼 크기를 구하는 재귀 수식을 유도하고, 이 수식의 해인 버퍼 크기 결정 수식을 유도한다. 또한, 버퍼 크기 결정 수식에서 사용될 미래의 버퍼 수를 예측하기 위해 예측 후 강제 전략을 제안한다. 이 전략에서는 관성적 가정들에 기반하여 미래에 할당될 버퍼 수를 예측하고, 실제 실행시간에 이 가정들이 만족되도록 한다. 이 전략에서는 새로 도착한 사용자 요청들이 이들 가정을 만족시키지 못하면, 이들 요청이 가정들을 만족시킬 때까지 서비스를 지연시킨다.
동적 버퍼 할당 기법은 버퍼 스케줄링 방식에 독립적이기 때문에 기존의 버퍼 스케줄링 방식에 모두 적용할 수 있다. 이를 보이기 위해, 본 논문에서는 동적 버퍼 할당 기법을 대표적 버퍼 스케줄링 방식인 라운드 로빈(BubbleUp) 방식, 스윕* 방식, 및 GSS* 방식에 적용하고, 각 방식에서의 최소 메모리 요구량을 정형적으로 분석한다.
본 논문에서는 분석과 시뮬레이션을 통해 동적 버퍼 할당 기법이 (서비스 중인 요청 수가 하나인 경우에서 최대 수인 경우까지를 평균한) 초기대기시간을 정적 버퍼 할당 기법에 비해 $\frac{1}{29.4} ~ \frac{1}{11.0}$로 줄이고, 메모리 요구량의 감소로 인해 (사용 가능한 시스템 메모리량별로 평균한) 동시 사용자 요청 수를 정적 버퍼 할당 기법의 $1.63 ~ 3.25$배로 증가시킴을 보인다.
다음으로, 본 논문에서는 버퍼 공유 전략에 메모리 공유 전략을 접목시킨 동적 버퍼 공유 기법(dynamic buffer sharing scheme)을 제안한다. 동적 버퍼 공유 기법은 기존 버퍼 공유 전략인 SMDP 알고리즘에 메모리 공유 전략을 사용하는 동적 버퍼 할당 기법을 적용한 기법이다. 이 기법은 메모리 공유 전략을 사용함과 동시에 동적 버퍼 할당 기법으로 작은 크기의 버퍼를 할당함으로써, SMDP 알고리즘에 비해 메모리 요구량을 크게 줄일 수 있다. 또한, 동적 버퍼 할당 기법을 사용함으로써, SMDP 알고리즘에서 새로운 사용자 요청을 고려하지 않고 버퍼 크기를 결정하여 서비스 중인 버퍼가 빌 수 있다는 문제를 해결한다. 본 논문에서는 시뮬레이션을 통해 동적 버퍼 공유 기법이 기존의 버퍼 공유 기법인 SMDP 알고리즘에 비해 메모리 요구량을 $\frac{1}{3.89} ~ \frac{1}{3.27}$로 줄임을 보인다.
본 논문의 결과를 종합하여 볼 때, 동적 버퍼 할당 기법과 동적 버퍼 공유 기법은 주문형 비디오 시스템의 성능과 용량을 크게 향상시킴을 알 수 있다.
