[논문]멀티미디어 스트리밍 서버를 위한 인기도 기반 인터벌 캐슁의 블록 수준 세분화 기법

권오훈; 김태석; 반효경; 고건

[국내논문] 멀티미디어 스트리밍 서버를 위한 인기도 기반 인터벌 캐슁의 블록 수준 세분화 기법
Block Level Refinement of Popularity-Aware Interval Caching for Multimedia Streaming Servers 원문보기

정보과학회논문지. Journal of KIISE. 시스템 및 이론, v.34 no.4, 2007년, pp.138 - 144

권오훈 (서울대학교 컴퓨터공학과) , 김태석 (서울대학교 컴퓨터공학과) , 반효경 (이화여자대학교 컴퓨터공학과) , 고건 (서울대학교 컴퓨터공학과)

초록
AI-Helper

최근 VOD(Video-On-Demand) 서비스가 널리 이용되면서 멀티미디어 스트리밍 서버를 위한 데이타 캐슁 기법의 중요성이 점점 증가하고 있다. 기존 연구를 통해 인터벌 캐슁 기법과 이를 객체의 인기도를 반영하도록 확장한 기법들이 다양한 환경에서 우수한 성능을 나타냄이 입증되었다. 본 논문에서는 이와 같은 기존의 기법을 블록 수준으로 세분화할 경우 멀티미디어 스트리밍 서버의 성능을 더욱 향상 시킬 수 있음을 보인다. 실제 VOD 서버의 트레이스를 이용한 시뮬레이션 실험을 통해 본 논문이 제안한 알고리즘이 캐쉬 적중률과 스트림의 초기 지연 시간을 향상시킴을 보인다.

Abstract ▼ AI-Helper

With recent proliferation of video-on-demand services, caching in a multimedia streaming server is becoming increasingly important. Previous studies have shown that request interval based caching and its extension for considering different video popularity performs well in various streaming environments. In this paper, we show that block level refinement of this existing scheme can further improve the performance of streaming servers. Trace driven simulations with real world VOD traces have shown that the proposed scheme improves the cache hit rate and the startup latency.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

하지만, PIC 기법에서는 시간이 흐르면서 가상 인터벌이 점차 멀티미디어 객체의 뒷부분으로 이동하여 초기 지연시간(startup latency)을 효과적으로 줄일 수 있는 객체의 시작 부분을 캐슁하지 못한다. 이에 본 논문에서는 PIC 기법을 블록 단위로 세분화하여 이러한 문제점을 해결하고 나아가 멀티미디어 스트리밍 서버의 성능을 향상 시킬 수 있는 인기도 기반 인터벌 캐슁의 블록 수준 세분화(Block Level Refinement of Popularity- Aware Interval Caching, B-PIC) 기법을 제안한다. 실제 VOD 트레이스를 사용한 시뮬레이션을 통해서 본 논문이 제안한 알고리즘이 캐쉬 적중률(hit ratio)과 시작 블록 미스(stard block misses)에 대해서 PIC 기법과 인터벌 캐슁, LRU(L留st Recently Used), MRU(Most Recently Used) 알고리즘보다 우수한 성능을 나타냄을 보인다.
본 장에서는 멀티미디어 스트리밍 서버를 위한 새로운 캐슁 기법을 제안한다. 3.
본 논문에서는 멀티미디어 스트리밍 서버를 위한 인기도 기반 인터벌 캐슁의 블록 수준 세분화 기법을 제안하였다. 새롭게 제안된 기법은 인터벌을 구성하는 일련의 블록 단위로 캐슁의 우선순위를 계산하는 기존의 기법들과 달리 인터벌을 구성하는 각각의 블록 단위로캐슁의 우선순위를 결정하여 더욱 높은 성능을 나타낼 수 있었다.

제안 방법

본 논문이 제안하는 B-PIC 기법에서는 PIC 기법과 마찬가지로 과거 참조 패턴을 분석해서 멀티미디어 객체의 미래 참조 시점을 예측한다. 하지만, PIC 기법과는 달리 인터벌을 단위로 캐슁 여부를 결정하는 것이 아니라 인터벌(가상 인터벌을 포함)을 구성하는 각각의 블록 단위로 캐슁 대상을 결정한다.
비교한다. 각 알고리즘의 성능 비교를 위해 트레이스기반 시뮬레이션을 통해 실험하였다. 또한 효율적인 실험을 위해서 두 곳의 상용 V0D 사이트(OnGameNet, Hanmir)로부터 추출한 실제 사용자 요청 트레이스를 사용하였다 H₃, 14] OnGameNet 트레이스는 293개의 비디오 파일을 가지 고았으며며, 이들 비디오 파일의 평균 실행 시간은 883초이다.

대상 데이터

각 알고리즘의 성능 비교를 위해 트레이스기반 시뮬레이션을 통해 실험하였다. 또한 효율적인 실험을 위해서 두 곳의 상용 V0D 사이트(OnGameNet, Hanmir)로부터 추출한 실제 사용자 요청 트레이스를 사용하였다 H₃, 14] OnGameNet 트레이스는 293개의 비디오 파일을 가지 고았으며며, 이들 비디오 파일의 평균 실행 시간은 883초이다. 비디오 파일에 대한 평균 요청 간격(inter-arrival time)은 6초이다.
표 1은 이들 트레이스의 특성을 정리한 것이다. B*IC과의 비교 대상으로는 PIC(Popularity- aware Interval Caching), ICdnterval Caching), LRU(Least Recently Used), MRUCMost Recently Used) 알고리즘 둥을 사용했다.

성능/효과

이에 본 논문에서는 PIC 기법을 블록 단위로 세분화하여 이러한 문제점을 해결하고 나아가 멀티미디어 스트리밍 서버의 성능을 향상 시킬 수 있는 인기도 기반 인터벌 캐슁의 블록 수준 세분화(Block Level Refinement of Popularity- Aware Interval Caching, B-PIC) 기법을 제안한다. 실제 VOD 트레이스를 사용한 시뮬레이션을 통해서 본 논문이 제안한 알고리즘이 캐쉬 적중률(hit ratio)과 시작 블록 미스(stard block misses)에 대해서 PIC 기법과 인터벌 캐슁, LRU(L留st Recently Used), MRU(Most Recently Used) 알고리즘보다 우수한 성능을 나타냄을 보인다.
하지만, 인터벌 캐슁과 거리 캐슁 기법은 짧은 기간 내의 두 연속적인 요청에 대한 시간 지역성(temporal locality)만을 고려하고 멀티미디어 객체의 서로 다른 인기도를 고려하지 않는다. 그 결과 멀티미디어 객체의 크기가 충분히 크지 않거나 스트림 요청 간의 인터벌이 매우 긴 경우캐슁의 효과를 얻을 수 없다. 이러한 문제점을 해결하기 위해 Kim 등은 인기도 기반의 인터벌 캐슁(Populaiity- aware Interval Caching, PIC) 기법을 제안하였다[7, 8].
캐쉬 적중률을 뜻한다. 즉, 이득 값이 큰 블록은 캐쉬에서 적중될 확률이 크고, 반대로 이득 값이 작은 블록은 캐쉬에서 적중될 확률이 작다. 따라서, 이득값이 큰 블록을 캐슁하는 것이 시스템의 성능 면에서 효과적이다.
그림 3은 이러한 문제점을 설명하고 있다. 그와 반대로, 본 논문이 제안한 B-PIC 기법에서는 시간이 흘러도 메모리 버퍼에 인기 있는 객체의 시작 부분 블록을 캐슁하고 있어서 인기 있는 객체의 초기 서비스 지연 시간을 줄일 수 있다. 결국 B-PIC 기법은 PIC 기법을 블록 수준에서 재정립함으로써, 캐슁의 이득을 극대화시킬 수 있다.
B-PIC 기법은 실제 요청이 발생하기 전에 인기 있는 멀티미디어 객체의 시작 부분을 캐슁하고있기 때문에 다른 캐슁 기법보다 훨씬 좋은 성능을 보이고 있다. PIC 기법도 실제 요청이 발생하기 전에 예측된 인터벌을 통해 객체의 시작 부분을 캐슁하기 때문에 인터벌 캐슁, LRU, MRU 기법보다는 좋은 성능을 보였다. 하지만, PIC 기법에서는 시간이 흐름에 따라 예측된 인터벌 구간이 점차 뒷부분으로 이동하기 때문에 B-PIC 기법보다 안 좋은 성능을 나타내었다.
하지만, PIC 기법에서는 시간이 흐름에 따라 예측된 인터벌 구간이 점차 뒷부분으로 이동하기 때문에 B-PIC 기법보다 안 좋은 성능을 나타내었다. B-PIC 기법은 인기 있는 멀티미디어 데이타의 시작 부분을 캐슁하기 때문에 시작 블록 미스 횟수에 대해서 기존의 PIC 기법보다 46.7%의 성능 향상을 보일 수 있었다.
1장에서 언급한 것과 마찬가지로 전통적인 버퍼 캐쉬 관리 기법인 LRU와 MRU는 본 실험에서 우수한 성능을 나타내지 못하였다. 본 논문이 제안한 B-PIC 기법은 두 개의 트레이스를 사용한 실험에서 모두 기존 캐슁 기법들에 비해 가장 우수한 성능을 나타내었다. 인터벌 캐슁 기법도 B-PIC 기법보다는 떨어지지만 다른 캐슁 기법보다 좋은 성능을 보이고 있다.
인터벌 캐슁 기법도 B-PIC 기법보다는 떨어지지만 다른 캐슁 기법보다 좋은 성능을 보이고 있다. PIC 기법은 OnGameNet 트레이스에서는 인터벌 캐슁 기법과 비슷한 성능을 나타내었지만, Hanmir 트레이스에서는 B-PIC과 인터벌 캐슁기법보다 낮은 성능을 나타내었다. 이는 Hanmir 트레이스의 요청 간격이 상대적으로 길고 그 편차 또한 크기 때문으로 분석할 수 있다.
새롭게 제안된 기법은 인터벌을 구성하는 일련의 블록 단위로 캐슁의 우선순위를 계산하는 기존의 기법들과 달리 인터벌을 구성하는 각각의 블록 단위로캐슁의 우선순위를 결정하여 더욱 높은 성능을 나타낼 수 있었다. 각 블록의 가치를 평가하는 데 있어서는 기대 참조 확률의 개념을 사용하였으며, 실제 인터벌뿐 아니라 인기 있는 멀티미디어 객체의 시작 부분을 캐슁하기때문에, 기존의 PIC, IC, LRU, MRU보다 캐쉬 적중률 및 시작 부분 미스에 대해서 우수한 성능을 나타내었다.
새롭게 제안된 기법은 인터벌을 구성하는 일련의 블록 단위로 캐슁의 우선순위를 계산하는 기존의 기법들과 달리 인터벌을 구성하는 각각의 블록 단위로캐슁의 우선순위를 결정하여 더욱 높은 성능을 나타낼 수 있었다. 각 블록의 가치를 평가하는 데 있어서는 기대 참조 확률의 개념을 사용하였으며, 실제 인터벌뿐 아니라 인기 있는 멀티미디어 객체의 시작 부분을 캐슁하기때문에, 기존의 PIC, IC, LRU, MRU보다 캐쉬 적중률 및 시작 부분 미스에 대해서 우수한 성능을 나타내었다. 특히, 시작 블록 미스에 관해서는 기존의 PIC 기법보다 46.
각 블록의 가치를 평가하는 데 있어서는 기대 참조 확률의 개념을 사용하였으며, 실제 인터벌뿐 아니라 인기 있는 멀티미디어 객체의 시작 부분을 캐슁하기때문에, 기존의 PIC, IC, LRU, MRU보다 캐쉬 적중률 및 시작 부분 미스에 대해서 우수한 성능을 나타내었다. 특히, 시작 블록 미스에 관해서는 기존의 PIC 기법보다 46.7%의 성능 향상을 나타내었다.

후속연구

이 기법은 우선 각각의 멀티미디어 객체에 대한 과거의 요청 간격을 통해 미래에 요청될 시간을 예측한다. 그리고, 멀티미디어 객체에 대한 실제 요청 시간들 간의 인터벌 뿐 아니라 실제 요청 시간과 예측된 요청 시간 간의 인터벌을 캐슁의 대상으로 함께 고려한다. 이는 인기 있는 멀티미디어 객체의 경우 요청이 들어오기 전에 앞부분이 미리 캐슁되도록 하여 인터벌 캐슁의 약점을 효율적으로 보완한다.
캐쉬는 디스크로부터 읽어 들인 데이타를 시간/공간 지역성을 고려해서 일정 기간 동안 메모리 내에 저장할 수 았는 공간을 말한다. 추후 동일한 데이타에 대한 입출력 요청이 있을 시, 디스크 입출력 없이 캐쉬 영역에서 서비스해줌으로써 시스템의 성능을 향상 시킬 수 있다. 또한, 디스크 입출력 작업은 상대적으로 큰 비용을 가지기 때문에, 입출력 작업 시 요청된 데이타만 읽어오는 게 아니라 그와 관련성이 있는 데이타도 미리 읽어 들인다.

참고문헌 (14)

A. Dan and D. Sitaram, 'Buffer Management Policy for an On-Demand Video Server,' IBM Research Report RC19347, T.J. Watson Research Center, Yorktown Heights, NY
A. Dan and D. Sitaram, 'A Generalized Interval Caching Policy for Mixed Interactive and Long Video Environments,' Proceedings of SPIE Multimedia Computing and Networking Conference, San Jose, CA, 1996
N. J. Sarhan and C. R. Das, 'Caching and Scheduling in NAD-Based Multimedia Servers,' IEEE Transactions on Parallel and Distributed Systems, Vol.15, No.10, pp.921-933, Oct. 2004

상세보기
J. M. Almeida, D. L. Eager, M. K. Vernon, 'A Hybrid Caching Strategy for Streaming Media Files,' Proceedings of the SPIE/ACM Conference on Multimedia Computing and Networking, 2001
B. Ozden, R. Rastogi and A. Silberschatz, 'Buffer Replacement Algorithms for Multimedia Storage Systems,' Proceedings of the 3rd IEEE International Conference on Multimedia Computing and Systems, Hiroshima, Japan, pp. 172-180, 1996
B. Ozden, R. Rastogi and A. Silberschatz, 'Disk Striping in Video Server Environments,' Proceedings of the 3rd IEEE International Conference on Multimedia Computing and Systems, Hiroshima, Japan, pp. 580-589, 1996
T. Kim, H. Bahn, and K. Koh, 'Popularity-Aware Interval Caching for Multimedia Streaming Servers,' IEE Electronics Letters, Vol.39, No.21, pp. 1555-1557, Oct. 2003

상세보기
T. Kim, H. Bahn, and K. Koh, 'Efficient Cache Management for QoS Adaptive Multimedia Streaming Services,' Lecture Notes in Computer Science, Springer-Verlag, Vol.3768, pp.1-11, Oct. 2005

상세보기
K. Lee, Y. Y. Park, H. Y. Yeom, 'Pre-emptive but safe interval caching for real-time multimedia system,' Int'l Journal of Computer Systems Science and Engineering, Vol. 18, No. 2, pp. 87-94, 2003
J. Fernandez, J. Carretero, F. Garcia-Carballeira, A. Calderon, and J. Perez-Menor, 'New stream caching schemas for multimedia systems,' IEEE Int'l Conf. Automated Production of Cross Media Content for Multi-Channel Dist., 2005
Sen, S., Rexford, J., and Towsley, D., 'Proxy prefix caching for multimedia streams,' IEEE INFOCOM'99, 1999
Eun-Ji Lim, Seong-Ho Park, Hyeon-Ok Hong, and Ki-Dong Chung, 'A proxy caching scheme for continuous media streams on the Internet,' 15th International Conference on Information Networking, pp. 720-725, 2001
OnGameNet Co. Ltd, http://www.ongamenet.com
Hanmir, Co. Ltd, http://www.hanmir.net

저자의 다른 논문 :

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증