비디오 프록시 서버에서의 저장 공간 확보를 위한 선택적 동영상 데이터 삭제 알고리즘
2010-03-04 CCTV뉴스
따라서 오랜 시간동안 사용자에 의해 요청되지 않은 동영상 데이터를 비디오 프록시 서버로부터 제거하는 삭제 알고리즘이 필요하다. 본 고에서는 사용자의 동영상 요청 패턴을 기반으로 하여 사용자에 의해 요청될 가능성이 가장 낮은 동영상을 선정하고 제거하는 효율적인 동영상 데이터 삭제 알고리즘을 제안한다.
제안하는 삭제 알고리즘은 비디오 프록시 서버의 공간 부족 시 저장되어 있는 동영상들을 요청된 순서로 정렬하고 여기서 가장 오래전에 사용자에 의해 요청되었던 동영상을 선정한다. 선정된 동영상에서 요청 가능성이 낮은 부분만이 선별되어 삭제됨으로써 비디오 프록시 서버의 저장 공간을 확보한다. 실험을 통해 제안하는 알고리즘이 기존의 알고리즘 보다 높은 적중률을 보이는 동시에 보다 적은 삭제 횟수를 보인다는 것을 확인한다.
광대역 망(broadband network)의 급속한 성장에 따라 인터넷을 통한 동영상 스트리밍(streaming) 기술은 빠르게 발전하고 있다. 그러나 현재 인터넷에서 제공되는 동영상 데이터 서비스의 품질은 크게 향상되지 않고 있는데 이는 실시간 전송을 위한 지연 시간의 요구사항을 충족시켜 주지 못하기 때문이다.
이와 같은 문제를 극복하기 위해 원거리에 위치하는 중앙 비디오 서버(central video server)의 입출력 대역폭(I/O bandwidth)을 증가시키는 방법을 사용하거나 또는 접근할 수 있는 사용자의 수를 제한하는 방법 등을 사용하고 있으나 이와 같은 방법은 대단히 제한적이며 안정적인 동영상의 전송을 보장하지 못한다.
최근에는 비디오 프록시 서버(video proxy server)를 사용자들과 근거리에 위치하여 활용함으로써 중앙 비디오 서버의 부하 감소와 초기 전송 지연(initial latency) 및 비디오 패킷 손실의 문제점을 해결하기 시작했다. 비디오 프록시 서버는 사용자들에 의해 요청되어지는 대용량의 동영상 데이터들을 복잡한 인터넷의 중간 경로를 거치지 않고 다수의 사용자들에게 직접 전달함으로써 데이터의 손실을 방지함과 동시에 보다 안정적이고 빠른 속도로 제공하는 것을 가능하게 한다.
그러나 비디오 프록시 서버는 중앙 비디오 서버의 저장 공간에 비해 비교적 제한된 용량을 가진다는 단점이 있다. 따라서 사용자에 의해 앞으로 요청될 가능성이 적은 동영상 데이터를 비디오 프록시 서버에서 삭제하는 동영상 데이터 알고리즘이 필요하다. 이를 위한 연구에서 가장 오래전에 접근한 동영상 데이터를 삭제하고 최근에 접근한 동영상 데이터만을 유지하는 Least Recently Used (LRU) 알고리즘이 제시되었다.
단, LRU 알고리즘은 요청된 시간만을 반영하고 접근 횟수를 반영하지 않기 때문에 최근에 한 번 요청된 동영상 데이터가 비디오 프록시 서버에 유지될 필요가 없음에도 불구하고 오랜 시간동안 해당 서버에 남아있게 되는 문제점을 가진다.
또 다른 대표적인 동영상 데이터 삭제 방법으로 가장 적게 사용된 동영상 데이터를 삭제 대상으로 선정하는 Least Frequently Used (LFU) 알고리즘이 있다. LFU는 참조 빈도(reference frequency)가 높은 동영상들만을 저장함으로써 LRU의 단점을 방지한다. 그러나 과거에 자주 요청되었던 동영상들로 인해 새롭게 요청되고 있는 동영상이 비디오 프록시 서버에 저장되지 못하는 문제점이 발생된다.
이와 같은 LRU와 LFU의 문제점들을 보완하기 위해 사용자 요청의 횟수와 시간을 동시에 고려하는 알고리즘인 interval caching과 distance caching 기법이 제안되었다. 그러나 이들 기법은 메모리를 기반으로 하기 때문에 텍스트나 이미지와 같은 적은 용량의 데이터들에 있어서는 적합하나 대용량의 동영상 데이터들에 있어서는 적합하지 않다.
최근의 연구에서 사용자가 주로 동영상의 시작 부분을 요청하는 접근 패턴을 가지며 비교적 짧은 지속시간을 가진다는 점이 제시되었다. 이를 활용하여 사용자가 요청한 동영상의 시작 부분인 prefix만을 비디오 프록시 서버에 저장 하는 prefix caching 기법이 제안되었다.
Prefix caching 기법은 사용자가 동영상을 요청했을 때 비디오 프록시 서버에 저장 되어있는 해당 동영상의 전반부인 prefix를 사용자에게 전송하여 초기 지연시간을 최소화하고 이와 동시에 원거리에 위치한 중앙 비디오 서버로부터 후반부인 suffix를 전송받는다. 그러나 아직까지 비디오 프록시 서버에 저장될 prefix의 크기를 결정하는 효과적인 방법이 제시되고 있지 못하다.
또 다른 최근 연구에서 일정 시간 동안에 발생한 사용자 접근 빈도수(access frequency)를 고려한 Partial Least Frequently Used (PLFU) 알고리즘과 사용자가 요청한 시간 정보를 활용하여 동영상 데이터를 비디오 프록시 서버에 저장하거나 삭제하는 Distance-based 알고리즘이 제안되었다.
그러나 이러한 방법들은 접근 빈도수나 접근 최근성(access recency)만을 활용한 방법으로 동영상 데이터의 사용자 요청과 관련된 정보들을 충분히 고려하고 있지 않다. 특히 사용자가 요청한 모든 동영상 데이터들이 비디오 프록시 서버에 저장되므로 한번 저장된 후 계속 요청되지 못하는 동영상 데이터 역시 비디오 프록시 서버에 저장되게 된다. 이는 곧 새로운 동영상 데이터의 저장을 위한 공간 부족 시에 과도한 동영상 데이터의 삭제가 수행되는 원인이 된다.
이러한 문제를 효율적으로 해결하기 위하여 본 고에서는 사용자가 요청한 동영상의 시간 정보와 요청 빈도수를 기반으로 앞으로 요청될 가능성이 낮은 동영상을 선정하고 제거함으로써 필요한 공간을 확보하는 비디오 프록시 서버에서의 동영상 데이터 삭제 알고리즘을 제안한다.
제안하는 알고리즘을 활용하면 한 번 요청되어 저장된 후 계속 서비스 되지 않는 동영상 데이터가 비디오 프록시 서버에서 우선 삭제되어 비디오 프록시 서버의 제한된 용량을 효율적으로 관리할 수 있게 된다. 또한 원격지에 위치한 중앙 비디오 서버로의 탐색 시간(seek time)을 줄일 수 있으므로 서비스 지연(service delay)을 줄일 수 있게 될 것이다.
제안하는 알고리즘을 위해 중앙 비디오 서버에서 동영상 데이터를 여러 개의 세그먼트(segment) 단위로 분할하여 전송하는 Chen 등이 제안한 피라미드식 미디어 분할(media segmentation) 기법이 사용된다. 미디어 분할 기법을 사용하면 적은 비용으로 많은 데이터를 신속하게 삭제하거나 저장할 수 있으므로 초기 지연과 네트워크의 트래픽을 효과적으로 줄여 주는 장점이 있다.
키 세그먼트를 활용한 선택적 동영상 삭제
본 고에서는 비디오 프록시 서버의 공간이 부족할 경우 공간을 확보하기 위한 방법은 두 단계과정으로 구성된다. 먼저 비디오 프록시 서버에 저장된 동영상 데이터를 공간 부족 시 우선적으로 삭제의 대상이 되는 삭제 세그먼트 그룹(delete segment group)과 요청의 가능성이 큰 보존 세그먼트 그룹(preserve segment group)의 두 그룹으로 구분한다. 다음으로 공간 확보를 위한 세그먼트 삭제 과정을 거친다.
저장된 세그먼트들을 두 그룹으로 구분하는 것은 삭제의 효율을 높일 수 있기 때문이다. 먼저 저장된 동영상의 세그먼트들을 두 그룹으로 구분하는 방법은 다음과 같다. 비디오 프록시 서버는 임의의 동영상의 각 세그먼트들을 대상으로 사용자가 요청한 횟수를 측정한 후 이를 활용하여 세그먼트 간의 요청 횟수 차이 값을 계산한다. 임의의 동영상에 대한 세그먼트의 요청 횟수 차이값 Li(k)는 식 (1)에 의해 주어진다.
Li(k)={ni(k-1)-ni(k)}, k=1,2,...,m (1)
여기서, ni(k)는 임의의 동영상 i의 세그먼트 k가 사용자에 의해 요청된 횟수이며 m은 하나의 동영상을 구성하는 세그먼트의 개수이다. 임의의 동영상에서 가장 큰 요청 횟수 차이 값을 가지는 세그먼트를 키 세그먼트(key segment)로 결정한다. 만일 세그먼트들의 요청 횟수 차이 값이 모두 동일할 경우 키 세그먼트를 마지막 이전의 세그먼트로 설정하고 마지막 세그먼트는 삭제 세그먼트 그룹으로 한다.
키 세그먼트는 임의의 동영상의 세그먼트들 중에서 사용자가 요청한 횟수가 가장 급격하게 감소하는 세그먼트이다. 따라서 비디오 프록시 서버는 이와 같이 결정된 키 세그먼트의 세그먼트 번호보다 낮은 세그먼트 번호를 가지는 세그먼트들을 보존 세그먼트 그룹으로 하고 높은 세그먼트 번호를 가지는 세그먼트들을 비디오 프록시 서버의 저장 공간 부족 시에 우선 삭제 할 수 있도록 삭제 세그먼트 그룹으로 분리한다. 그림 1은 키 세그먼트를 활용하여 임의의 동영상의 세그먼트들을 보존 세그먼트 그룹과 삭제 세그먼트 그룹으로 구분하는 것을 보인다.
[그림 1] 키 세그먼트를 활용한 세그먼트 분리
비디오 프록시 서버의 여유 공간을 확보를 위한 방법은 비디오 프록시 서버에 저장 되어있는 가장 큰 세그먼트의 크기보다 저장 공간이 작을 경우에 수행한다. 이는 새로운 세그먼트의 입력으로 비디오 프록시 서버 저장 공간의 부족 현상이 발생한 시점에서 공간 확보를 수행할 경우 저장 공간을 초과하여 동영상들이 입력되는 오버플로(overflow)의 발생을 방지하기 위한 것이다.
세그먼트 그룹 분리 방법을 활용하여 비디오 프록시 서버의 여유 공간을 확보하기 위해 동영상 세그먼트들을 삭제하는 알고리즘은 다음과 같다.
(ⅰ) 비디오 프록시 서버는 저장되어 있는 동영상들의 마지막 세그먼트가 요청된 시간이 오래된 순으로 정렬한 후 가장 오래전에 요청된 동영상을 선정하고 이 동영상에 대하여 위에서 제시된 세그먼트 그룹 분리 방법을 활용하여 보존 세그먼트 그룹과 삭제 세그먼트 그룹으로 분리한다.
(ⅱ) 삭제 세그먼트 그룹의 크기가 필요한 비디오 프록시 서버 저장 공간의 크기보다 크다면 해당 세그먼트 그룹의 마지막 세그먼트만을 삭제한다. 그러나 삭제 세그먼트 그룹의 크기가 필요한 비디오 프록시 서버 저장 공간의 크기보다 작다면 삭제 세그먼트 그룹의 전체를 삭제한 후 정렬된 동영상 리스트에서 삭제가 수행된 동영상 다음에 위치한 동영상을 선정하고 위의 삭제하는 과정을 반복한다. 이와 같이 삭제 세그먼트 그룹에 포함된 작은 크기의 세그먼트들을 한 번에 모두 삭제함으로써 공간 확보를 위해 발생되는 불필요한 삭제 수행 횟수가 증가되지 않는 장점을 가진다.
(ⅲ) 삭제 알고리즘의 수행 과정에서 비디오 프록시 서버에 저장되어 있는 동영상들의 삭제 세그먼트 그룹들이 모두 삭제된 경우 과정 (ⅰ)에서 정의된 동영상 리스트에서 가장 오래전에 요청된 동영상을 선정한 후 선정된 동영상의 보존 세그먼트 그룹에서 세그먼트 번호가 가장 높은 세그먼트를 삭제한다.
(ⅳ) 가장 오래전에 요청된 세그먼트의 보존 세그먼트 그룹에서 세그먼트 번호가 가장 높은 세그먼트의 삭제 후에도 비디오 프록시 서버에 충분한 저장 공간이 확보되지 않을 경우 과정 (ⅰ)에서 구한 동영상 리스트에서 삭제가 수행된 동영상 다음에 위치하는 동영상을 재선정하고 삭제하는 과정을 반복한다.
[그림 2] 제안하는 동영상 데이터 삭제 알고리즘
그림 2는 제안하는 비디오 프록시 서버에서의 동영상 데이터 삭제 알고리즘을 나타내는 전체 플로차트이다.
실험
제안하는 동영상 데이터 삭제 알고리즘의 성능 평가를 위해서 기존의 알고리즘인 PLFU(Partial Least Frequently Used)와 Distance-based 방법 그리고 Reallocation Affinity 방법을 대상으로 비디오 프록시 서버의 저장 공간 크기 변화에 따른 블록 적중률(block hit rate)과 블록 삭제 횟수(number of block deletion)를 비교한다.
또한 제안하는 방법의 보다 정확한 성능 평가를 위해 본 고에서는 그림 3과 같이 세그먼트에 포함되는 블록의 수가 세그먼트 번호의 2의 지수배로 증가하는 피라미드식 분할(pyramid segmentation) 방법을 활용하여 동영상을 구성하고 실험한다. 또한 실험을 위해 분 당 120회의 요청 횟수로 사용자가 원하는 동영상 데이터가 무작위로(randomly) 요청된다. 표 1은 실험을 수행하기 위한 조건이다.
[그림 3] 미디어 분할: 피라미드식 분할
[그림 4] 비디오 프록시 서버 저장 공간의 크기 변화에 따른 기존 알고리즘과의 블록 적중률 비교
[그림 5] 비디오 프록시 서버 저장 공간의 크기 변화에 따른 기존 알고리즘과의 블록 삭제 횟수 비교
그림 4는 본 고에서 제안하는 동영상 데이터 삭제 알고리즘을 활용하여 기존의 방법인 PLFU와 Distance -based 방법 그리고 Reallocation Affinity 방법과 블록 적중률의 비교를 보인다. 실험 결과를 통해 기존의 방법들에 비해 비교적 높은 블록 적중률을 보임으로서 제안하는 비디오 프록시 서버에서의 삭제 알고리즘이 사용자에 의해 향후 요청될 가능성이 적은 동영상 데이터들을 선별하여 삭제하고 있음을 알 수 있다.
제안하는 방법의 효율성을 보다 정확하게 확인하기 위해 그림 5와 같이 비디오 프록시 서버 저장 공간의 크기 변화에 따른 블록 삭제 횟수를 실험한다. 실험 결과를 통해 제안하는 방법이 기존 방법들에 비해 비교적 적은 블록 삭제 횟수를 보이는 것을 확인할 수 있다.
이를 통해 제안하는 방법이 사용자에 의해 요청될 가능성이 적은 동영상 데이터들만을 대상으로 삭제 알고리즘을 수행하고 자주 요청하는 동영상의 세그먼트들만을 비디오 프록시 서버에 저장하도록 함으로서 해당 저장 공간에서 수행되는 블록 삭제 횟수를 효과적으로 감소시키고 있음을 알 수 있다.
그림 4와 5의 실험 결과를 통해 기존 방법들에 비해 제안하는 방법이 높은 블록 적중률과 적은 블록 삭제 횟수를 나타낸다는 것을 확인할 수 있다. 이는 사용자가 계속해서 요청하는 동영상 데이터들이 비디오 프록시 서버에 미리 저장되며 사용자의 요구에 신속하고 안정적인 서비스를 제공할 수 있다는 것을 의미한다.
결론
통신 기술의 급속한 발전에 힘입어 네트워크를 통한 실시간 동영상 서비스가 보편화 되고 있다. 현재 인터넷 상에서 이루어지는 동영상 데이터의 활용에 있어 가장 중요한 점은 그 품질을 보장 할 수 있어야 한다는 것이다. 현재의 동영상 전송은 손실과 지연에 상당히 민감하게 반응하여 이를 기반으로 한 여러 분야의 발전에 커다란 문제점으로 지적되고 있다.
이와 같은 문제를 해결하기 위해 사용자들과 근거리에 위치한 비디오 프록시 서버를 활용하여 인터넷 VOD(Video-On- Demand) 서비스의 품질을 크게 개선시킬 수 있다. 그러나 비디오 프록시 서버는 비교적 제한된 용량을 가진다는 단점이 있다.
따라서 본 고에서는 원격지에 위치하는 중앙 비디오 서버에 비해 상대적으로 제한된 저장 공간을 가지는 비디오 프록시 서버의 저장 공간 부족 시에 사용자들에 의해 요청될 가능성이 낮은 동영상을 선정하고 제거하는 효율적인 동영상 데이터 삭제 알고리즘을 제안하였다.
비디오 프록시 서버 저장 공간의 크기를 변화시켜가며 수행한 실험을 통해 제안하는 방법은 기존의 방법들에 비해서 높은 블록 적중률과 적은 블록 삭제 횟수를 나타냄으로써 보다 더 효율적임을 확인한다.
<본 내용은 전자공학회 논문지 제 46권 CI편을 바탕으로 정리한 것입니다>