[논문]풀 기반 데이타 방송 시스템에서의 데이타 인기도를 고려한 캐싱 전략

신동천

풀 기반 데이타 방송 시스템에서의 데이타 인기도를 고려한 캐싱 전략
A Caching Strategy Considering Data Popularity in Pull-Based Data Broadcast Systems 원문보기

정보과학회논문지. Journal of KIISE. 정보통신, v.33 no.4, 2006년, pp.324 - 332

초록
AI-Helper

캐싱은 데이타 방송 시스템에서 방송 요청의 경쟁을 줄임으로써 좁은 대역폭으로 인한 시스템 성능의 저하를 완화할 수 있는 유용한 방법이다. 본 논문에서는, 풀 기반 방송 시스템에서 클라이언트들간의 데이타 인기도를 반영하는 캐싱 전략을 제안한다. 아울러, 데이타 방송 버전을 이용하여 데이타 접근의 최근성을 반영할 수 있도록 하고 제안한 전략의 성능을 시뮬레이션을 통하여 평가한다. 성능 평가에 따르면, 히트율과 미스 비용을 함께 고려한 전략이 전통적 전략인 LRU 보다 성능 우위를 보이고 있다. 클라이언트들의 데이타 인기도를 고려한 전략은 일부 경우에 있어 성능 우위를 보여 주고 있다.

Abstract ▼ AI-Helper

A caching is a useful technique to alleviate performance degradation due to the inherent narrow bandwidth by reducing contention of broadcast requests. In this paper, we propose a caching strategy for pull-based data broadcast system which considers data popularity among clients. In addition, the proposed strategy also reflects recentness of data access based on data broadcast version. Then, we evaluate the performance of proposed strategy through a simulation approach. According to the results, the strategy considering both hit ratio and miss cost shows better performance than the traditional LRU. In addition, the strategy considering data popularity among clients shows better performance in some cases.

주제어

AI 본문요약
AI-Helper

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

문제 정의

데이타 방송 시스템에서 효율적인 캐싱 전략은 히트율 향상뿐만 아니라 미스에 따른 비용도 줄여야 한다고 지적하였다. 또한, 클라이언트들의 데이타에 대한 인기도를 반영함으로써 가까운 미래에 필요로 할 수 있는 데이타를 미리 캐싱하는 일이 필요함도 지적하였다. 이러한 원칙을 반영하는 캐싱 전략을 제시하기 전에 히트율과 미스 비용에 관련한 몇 가지 직관을 제시한다.
데이타 방송 시스템에서 캐싱 전략은 기존의 전략과 는 달리 히트율뿐만 아니라 미스에 따른 비용을 줄일 수 있는 전략이 필요함은 널리 알려진 사실이다. 본 논문에서는 미스 비용을 줄일 수 있는 전략이 필요함을 실험을 통해 입증하였다. 또한, 클라이언트들의 데이타 인기도를 캐싱 전략에 반영하여 미리 캐싱하는 효과를 얻을 수 있는 전략을 제시하고 그 효과를 성능 평가를 통해 알아보았다.
본 논문에서는 풀 기반의 시스템에서 클라이언트 자신이 유지하는 정보만 고려하는 기존의 연구와 달리 서버로부터 얻을 수 있는 정보인 클라이언트들의 데이 타 인기도를 반영하는 캐싱 전략을 제안한다. 아울러, 전통적인 시스템에서 대표적인 캐싱 전략인 LRU(Least Recently Used) 전략의 특징인 데이타 접근의 최근성을 데이타 방송 시스템에서 효과적으로 반영하기 위하여 데이타 방송 버전을 고려한다.

가설 설정

.H₁: 데이타 접근 빈도수가 높은 데이타는 캐시에 존재할 필요가 있다.
.H₃: 높은 데이타 인기도를 갖는 데이타는 캐쉬에 존재할 필요가 있다.
・H₂: 대기 시간이 큰 데이타는 캐시에 존재할 필요가 있다.

제안 방법

아울러, 전통적인 시스템에서 대표적인 캐싱 전략인 LRU(Least Recently Used) 전략의 특징인 데이타 접근의 최근성을 데이타 방송 시스템에서 효과적으로 반영하기 위하여 데이타 방송 버전을 고려한다. 그리고, 제안한 캐싱 전략에서 인기도의 고려가 성능에 미치는 영향을 시뮬레이션을 통하여 분석하고 평가한다.
시뮬레이션 결과의 정확성을 제고시키기 위해서 각 시뮬레이션의 초기 단계에 수집된 자료는 결과에 반영하지 않았으며, 또한 각 시뮬레이션에 대해 난수 생성기의 시드 값을 변경시키면서 여러 차례 반복 실험한 결과에 대한 평균을 이용하여 최종 결과를 산출하였다. 데 이 타 방송 시스템 환경에서는 전통적 시스템 환경과는 달리 히트율(%)이 아니라 캐시 미스에 따른 대기 시간의 고려가 성능에 커다란 영향을 주므로 성능 척도로는 평균 응답 시간(시뮬레이션 시간)을 사용하였다. 캐싱 전략에서 캐쉬 크기에 대한 각 전략들의 성능을 비교하기 위하여 우선 캐쉬 크기를 변화시키면서 실험을 하였다.
본 논문에서는 미스 비용을 줄일 수 있는 전략이 필요함을 실험을 통해 입증하였다. 또한, 클라이언트들의 데이타 인기도를 캐싱 전략에 반영하여 미리 캐싱하는 효과를 얻을 수 있는 전략을 제시하고 그 효과를 성능 평가를 통해 알아보았다.
본 논문에서는 데이타 접근의 최근성을 반영하기 위해 서버로부터 데이타가 방송될 때 데이타와 함께 받는 방송 버전번호를 이용한다. 방송 버전번호는 매 방송 주기마다 1씩 증가하는 값으로 정의한다.
본 논문에서는 풀 기반의 시스템에서 클라이언트 자신이 유지하는 정보만 고려하는 기존의 연구와 달리 서버로부터 얻을 수 있는 정보인 클라이언트들의 데이 타 인기도를 반영하는 캐싱 전략을 제안한다. 아울러, 전통적인 시스템에서 대표적인 캐싱 전략인 LRU(Least Recently Used) 전략의 특징인 데이타 접근의 최근성을 데이타 방송 시스템에서 효과적으로 반영하기 위하여 데이타 방송 버전을 고려한다. 그리고, 제안한 캐싱 전략에서 인기도의 고려가 성능에 미치는 영향을 시뮬레이션을 통하여 분석하고 평가한다.
클라이언트마다 선호하는 데이타를 다르게 만들기 위해서 각 클라이언트가 일정기간 동안 액세스하는 데이 타의 범위 (acc_range)를 1000으로 설정하여 전체 5000개의 데이타 페이지 중 1000개에 해당되는 부분만 액세스하도록 하였다. 이 1000개의 데이타 페이지 중에서 집중적으로 액세스하는 부분(hotarea_size)을 100으로 정 하여 hotacc_rate의 값을 조정함으로써 각 클라이언트가 선호하는 데이타 페이지를 원하는 값으로 조절할 수 있도록 하였다. hotacjrate는 클라이언트의 핫 영역 접근 비율로 0.
이러한 가중치 설정 문제는 최적화 문제이므로 또 다른 문제가 된다. 이러한 이유로 본 논문에서는 데이타 접근의 최근성과 대 기 시간의 최근성을 반영하기 위해 방송 버전 번호 같은 다른 방안을 사용한다. AWT 전략의 제시는 데이타 인기도를 고려한 전략이 그렇지 않은 전략에 비해 성능에 어떠한 영향을 미치는지를 분석하기 위해 제시되었으며 평가 대상으로 선정하였다.
제안한 캐싱 전략들을 기존의 LRU 전략의 성능을 시뮬레이션을 통하여 평가하였다. 시뮬레이션 모델은 그림 2와 같으며 CSIM[14]을 이용하여 구현하였다.
데 이 타 방송 시스템 환경에서는 전통적 시스템 환경과는 달리 히트율(%)이 아니라 캐시 미스에 따른 대기 시간의 고려가 성능에 커다란 영향을 주므로 성능 척도로는 평균 응답 시간(시뮬레이션 시간)을 사용하였다. 캐싱 전략에서 캐쉬 크기에 대한 각 전략들의 성능을 비교하기 위하여 우선 캐쉬 크기를 변화시키면서 실험을 하였다. 그림 3은 캐쉬 크기 변화에 따른 전략들의 성능을 보여 주고 있다.
클라이언트는 자신이 필요로 하는 데이타가 캐시에 포함되어 있지 않을 경우 서버에 해당 데이타를 직접 요청하여 얻게 되는데 이러한 요청은 서버의 큐에 보관되어 처리된다. 클라이언트가 제기한 데이타의 요청에 대해 해당 데이타를 얻은 후에 일정한 시간이 경과 하는 동안 새로운 연산을 제기하지 않도록 하기 위해서 think_time을 3으로 설정하였다.
클라이언트마다 선호하는 데이타를 다르게 만들기 위해서 각 클라이언트가 일정기간 동안 액세스하는 데이 타의 범위 (acc_range)를 1000으로 설정하여 전체 5000개의 데이타 페이지 중 1000개에 해당되는 부분만 액세스하도록 하였다. 이 1000개의 데이타 페이지 중에서 집중적으로 액세스하는 부분(hotarea_size)을 100으로 정 하여 hotacc_rate의 값을 조정함으로써 각 클라이언트가 선호하는 데이타 페이지를 원하는 값으로 조절할 수 있도록 하였다.
풀 기반 데이타 방송 시스템을 위한 캐싱 전략에서 클라이언트들의 데이타 인기도를 고려하는 전략의 차별성을 위해 기존의 주요 캐싱 전략을 간략히 소개한다. .

대상 데이터

이러한 이유로 본 논문에서는 데이타 접근의 최근성과 대 기 시간의 최근성을 반영하기 위해 방송 버전 번호 같은 다른 방안을 사용한다. AWT 전략의 제시는 데이타 인기도를 고려한 전략이 그렇지 않은 전략에 비해 성능에 어떠한 영향을 미치는지를 분석하기 위해 제시되었으며 평가 대상으로 선정하였다.

데이터처리

시뮬레이션 결과의 정확성을 제고시키기 위해서 각 시뮬레이션의 초기 단계에 수집된 자료는 결과에 반영하지 않았으며, 또한 각 시뮬레이션에 대해 난수 생성기의 시드 값을 변경시키면서 여러 차례 반복 실험한 결과에 대한 평균을 이용하여 최종 결과를 산출하였다. 데 이 타 방송 시스템 환경에서는 전통적 시스템 환경과는 달리 히트율(%)이 아니라 캐시 미스에 따른 대기 시간의 고려가 성능에 커다란 영향을 주므로 성능 척도로는 평균 응답 시간(시뮬레이션 시간)을 사용하였다.

이론/모형

제안한 캐싱 전략들을 기존의 LRU 전략의 성능을 시뮬레이션을 통하여 평가하였다. 시뮬레이션 모델은 그림 2와 같으며 CSIM[14]을 이용하여 구현하였다.

성능/효과

그러나 그렇지 못한 경우에는 오히려 AWT보다 낮은 성능을 보여 주어 데이타 방송 시스템에서 캐싱 전략 수립을 위해 여러가지 요소를 복합적으로 고려하는 것이 성능 우위를 항상 보여 주지는 않음을 알 수 있다. 또한, 데이타 방송 시스템의 성능은 캐싱 전략에도 영향을 받지만 데이타 방송 알고리즘과 같은 요인에 의해 크게 좌우될 수 있음을 알 수 있다. 따라서, 효율적인 캐싱 전략은 데이타 방송 알고리즘의 특성을 고려하여 반영하는 전략이어야 함을 입증한다고 할 수 있다.
결국, 미리 캐싱하는 효과를 보지 못함에도 불구하고 이를 위한 요소인 데이타 인기도를 고려하게 됨에 따라 캐싱 전략이 비효율적으로 운영되기 때문으로 판단된다. 이 결과는 데이타 방송 시스템을 위한 캐싱 전략 수립에서 캐싱 전략에 영향을 줄 수 있는 여러 요소들을 복합적으로 고려하는 것이 반드시 좋은 전략이 될 수 없음을 입증하고 있다.
즉, 데이타 접근의 최근성을 고려할 필요가 있다. 접근의 최근성을 고려함으로써 최근에 증가하는 데이타 접근 빈도수를 갖는 데이타가 최근에 감소하는 데이다 접근 빈도수를 갖는 데이타보다 캐 쉬에 존재할 확률을 높일 수 있다.
식 (1) 로부터 동일한 접근 수를 갖는다 하여도 최근에 접근 빈도수가 많은 데이타가 더 큰 접근 빈도수를 갖게 됨을 알 수 있다. 특히, 방송 버전번호를 이용함으로써 각 데이타 접근의 최근성 반영에 점진적인 가중치를 적용하고 있는 효과를 볼 수 있음을 알 수 있다.

참고문헌 (14)

D. Barbara, 'Mobile Computing and Databases-A Survey:' IEEE Transactions on Knowledge Engineering, Vol. 11, No, 1, pp. 108-117, J999

상세보기
S. K. Madria and B. K. Bhargava, 'A Transaction Model to Improve Data Availability in Mobile Computing,' Journal of Distributed and Parallel Databases, Vol. 10, No. 2, pp, 127-160, 2001
S. Acharya, M. Franklin, and S. Zdonik, 'Balancing Push and Pull for Data Broadcast,' Proc. of ACM SIGMOD, pp, 183-194, 1997

상세보기
T. Choi, Y. Kim, K. Chung, 'A Prefetching Scheme based on the Analysis of User Access Patterns in News-On-Demand System,' Proc. of ACM Int. Conf. on Multimedia, pp. 145-148, 1999
C. Griwodz, M. Bar, L. C. Wolf, 'Long-term movie popularity models in video-on-demand systems: or the life of an on-demand movie,' Proc. of ACM Int. Conf. on Multimedia, pp. 349-357, 1997
K. Y. Lai, Z. Tari, and P. Bertok, 'Cost Efficient Broadcast based Cache Invalidation for Mobile Environments,' Proc. of ACM Symposium on Applied Computing, pp. 871-877, 2003
X. Shao and Y. Lu, 'Maintain Cache Consistency of Mobile Database Using Dynamical Periodical Broadcast Strategy,' Proc of Int. Conf. on Machine Learning and Cybernetics, pp. 2389-2393, 2003
S. Galvin and P. B. Galvin, Operation System Concepts, 4th Edition, Addison Wesley, 1994
S. Khanna and V. Liberatore, 'On Broadcast Disk Paging,' Proc. of ACM Symposium on the Theory of Computing, pp. 634-643, 1998
Y. J. Lee and D. C. Shin, 'Performance of Caching Strategies for Pull-based Data Broadcast Systems in Mobile Computing Environments,' Journal of Computer Information Systems, Vol. 15, No. 4, pp. 102-115, 2005
V. Liberatore, 'Caching and Scheduling for Broadcast Disk Systems,' Technical Report 98-71, UMIACS, 1998
J. Xu, Q., Hu, W.-C. Lee, and D. L. Lee. 'Performance Evaluation of Optimal Cache Replacement Policy for Wireless Data Dissemination,' IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 1, pp. 125-139, 2004

상세보기
D. Aksoy and M. Franklin, 'RxW: A Scheduling Approach for Large-Scale Data Broadcast,' IEEE/ACM Transactions on Networking, Vol. 7, No.6, pp. 846-860, 1999

상세보기
H. Schwetman, CSIM User's Guide for Use with CSIM Revision 16, Microelectronics and Computer Technology Corporation, 1992

저자의 다른 논문 :

표제어: 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

연합인증