KR20070117874A

KR20070117874A - 이동망 시스템의 능동적 캐쉬 제어 방법, 그 기록 매체 및그 시스템

Info

Publication number: KR20070117874A
Application number: KR20060052048A
Authority: KR
Inventors: 이상근; 최재호
Original assignee: 고려대학교 산학협력단
Priority date: 2006-06-09
Filing date: 2006-06-09
Publication date: 2007-12-13
Anticipated expiration: 2026-06-09
Also published as: KR100791628B1

Abstract

이동망 시스템의 능동적 캐쉬 제어 방법, 그 기록 매체 및 그 시스템이 개시된다.

본 발명은 서버의 데이터들이 업데이트된 시간에 대한 가중 평균인 업데이트 히스토리를 포함한 업데이트 리스트를 수신하는 단계, 상기 클라이언트에서 임의의 데이터에 대한 질의가 발생하면, 상기 데이터를 상기 캐쉬에서 검색하는 단계, 상기 캐쉬에 상기 데이터가 존재하는 경우, 상기 서버로부터 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 상기 업데이트 히스토리 초과이면 상기 서버로부터 다음 업데이트 리스트를 수신하고, 상기 경과된 시간이 상기 업데이트 히스토리 이하이면 상기 캐쉬에 존재하는 데이터를 독출하는 단계 및 상기 다음 업데이트 리스트에 상기 데이터가 존재하면, 상기 데이터를 상기 서버에 요청하는 단계를 포함한다.

본 발명에 의하면, 모바일 환경에서 질의가 발생했을 때, 클라이언트들이 자신의 캐쉬를 단시간내에 사용할 수 있게 함으로써, 불필요한 응답 지연시간을 줄이고, 캐쉬내에 요청한 데이터가 존재할 경우 질의에 대한 응답을 곧바로 얻을 수 있기 때문에, 캐쉬 사용률을 높임으로써 캐쉬 가용성을 높일 수 있으며, 허위경보(false alarm) 문제를 제거할 수 있다.

Description

이동망 시스템의 능동적 캐쉬 제어 방법, 그 기록 매체 및 그 시스템 {Method for active controlling cache in mobile network system, Recording medium and System thereof}

도 1은 종래의 IR 기반의 방법에서 질의를 요청하고 응답을 받는 과정을 도시한 것이다.

도 2는 종래의 UIR 기반의 방법에서 질의를 요청하고 응답을 받는 과정을 도시한 것이다.

도 3은 종래의 UIR 기반의 방법에서 불필요한 응답지연이 일어나는 상황의 예를 도시한 것이다.

도 4는 본 발명이 적용되는 브로드 캐스트 환경을 간단하게 도식화한 것이다.

도 5는 본 발명에서 질의를 요청하고 응답을 받는 과정을 도시한 것이다.

도 6은 발명에 따른 이동망 시스템의 블럭도이다.

도 7은 발명에 따른 이동망 시스템의 능동적 캐쉬 제어 방법의 흐름도이다.

도 8은 종래의 캐쉬 제어 방법 및 본 발명에 따른 평균 응답 시간을 나타낸 그래프이다.

본 발명은 모바일 컴퓨팅 환경에 관한 것으로, 이동망 시스템의 능동적 캐쉬 제어 방법, 그 기록 매체 및 그 시스템에 관한 것이다.

셀룰러 폰. PDA등과 같은 모바일 기기 사용증가에 따라 더욱 많은 서비스들의 무선환경을 통해 서비스될 것으로 예상되고 있다. 그러나, 이러한 서비스들은 좁은 대역폭, 제한된 배터리 용량, 잦는 클라이언트의 접속단절 등의 모바일 환경으로 인한 제약 사항들을 가진다. 모바일 환경에서 자주 사용하는 데이터를 사용자의 저장공간 즉 사용자의 캐쉬에 저장하는 것은 제한된 배터리 사용을 효율적으로 하고 좁은 대역폭 사용을 위한 경쟁을 줄이기 위한 효율적인 방법이다.

그러나, 캐쉬에 저장된 데이터는 원본 데이터는 업데이트 되었지만, 복사본은 업데이트 되지 않을 수도 있기 때문에 무효화될 수 있으며, 그 결과 사용자는 자신의 캐쉬를 바로 사용할 수 없다. 최근 많은 연구에서 IR기반의 캐쉬무효화 방법들이 그 확장성 때문에 매우 효과적인 방법임을 증명되었다.

인밸리데이션 리포트(Invalidation Report, IR) 기반의 방법은 긴 응답시간과 낮은 캐쉬 가용성을 가지며, 많은 경우에 사용자들은 특정한 시간 안에 데이터를 얻어야 한다.

특정한 시간안에 데이터를 얻었다 할지라도 불필요한 응답시간 지연을 일으 키는 허위경보(false alarm)문제가 발생할 수도 있다. 많은 연구들이 이러한 긴 응답시간을 줄이기 위해 이루어져 왔다. 이러한 연구들에서는 업데이티드 인밸리데이션 리포트(Updated Invalidation Report, UIR)이 사용되었다.

예를 들어, 클라이언트가 D1 이라는 데이터가 필요할 때, D1이 자신의 캐쉬에 있으면, 자신이 가지고 있는 데이터가 서버의 데이터와 동일한지 확인한다. 먼저, 서버는 업데이트 된 데이터의 ID를 주기적으로 방송한다. 업데이트된 데이터의 ID는 IR과 UIR에 포함되어 있다. 클라이언트는 D1 이라는 데이터가 자신의 캐쉬에 있으면, 다음 IR이나 UIR을 확인한 후, 업데이트 되지 않았다면, 캐쉬에 있는 D1을 사용한다. 업데이트 되었다면, 서버에 D1 이라는 데이터를 요청하고 다음 IR이후에 요청한 데이터를 받는다.

데이터 d_x가 캐쉬에 있으며, 시점 A에서 업데이트 되었을 때와 시점 B에서 업데이트 되었을 때, 모두 T_i,2에서 브로드 캐스트되는 UIR은 d_x가 업데이트 되었다는 정보를 포함하게 된다.

만일 A와 B사이에서 캐쉬에 있는 d_x를 사용하게 된다면, B에서 업데이트가 일어났을 경우에 종래의 UIR 기반의 방법에서는 UIR을 확인하여 업데이트가 되었으 면, 서버에 데이터를 요청하고, 요청한 데이터를 다음 IR 뒤에서 수신한다.

그러나, 실제 데이터가 캐쉬에 있는지 사용자가 확인한 시점에는 업데이트는 일어나지 않았다. 즉, 캐쉬에 있는 데이터는 그 시점에는 최신의 데이터이다. 따라서, UIR 기반의 방법에 따르면, 허위경보(false alarm)를 클라이언트에게 주게 된다.

따라서, 종래의 캐쉬 제어 방법은 클라이언트가 수동적으로 IR 또는 UIR을 기다리기만 하므로, 불필요한 응답 시간 지연, 낮은 캐쉬 가용성을 갖게되고, 허위경보(false alarm) 등이 발생하는 문제점이 있다.

본 발명이 이루고자 하는 첫번째 기술적 과제는 불필요한 응답 지연시간을 줄이고, 캐쉬 가용성을 높이며, 허위경보(false alarm) 문제를 제거할 수 있는 이동망 시스템의 능동적 캐쉬 제어 방법을 제공하는데 있다.

본 발명이 이루고자 하는 두번째 기술적 과제는 상기의 이동망 시스템의 능동적 캐쉬 제어 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공하는데 있다.

본 발명이 이루고자 하는 세번째 기술적 과제는 상기의 이동망 시스템의 능동적 캐쉬 제어 방법이 적용된 캐쉬를 능동적으로 제어하는 이동망 시스템을 제공하는데 있다.

상기의 첫번째 기술적 과제를 이루기 위하여, 본 발명은 캐쉬를 내장한 클라 이언트와 업데이트 리스트를 브로드캐스트 하는 서버를 포함하는 이동망 시스템에 있어서, 상기 서버의 데이터들이 업데이트된 시간에 대한 가중 평균인 업데이트 히스토리를 포함한 업데이트 리스트를 수신하는 단계, 상기 클라이언트에서 임의의 데이터에 대한 질의가 발생하면, 상기 데이터를 상기 캐쉬에서 검색하는 단계, 상기 캐쉬에 상기 데이터가 존재하는 경우, 상기 서버로부터 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 상기 업데이트 히스토리 초과이면 상기 서버로부터 다음 업데이트 리스트를 수신하고, 상기 경과된 시간이 상기 업데이트 히스토리 이하이면 상기 캐쉬에 존재하는 데이터를 독출하는 단계 및 상기 다음 업데이트 리스트에 상기 데이터가 존재하면, 상기 데이터를 상기 서버에 요청하는 단계를 포함하는 이동망 시스템의 능동적 캐쉬 제어 방법을 제공한다.

또한, 상기의 첫번째 기술적 과제를 이루기 위하여, 본 발명은 캐쉬를 내장한 클라이언트와 업데이트 리스트를 브로드캐스트 하는 서버를 포함하는 이동망 시스템에 있어서, 상기 클라이언트에서 임의의 데이터에 대한 질의가 발생하면, 상기 데이터를 상기 캐쉬에서 검색하는 단계, 상기 캐쉬에 상기 데이터가 존재하는 경우, 상기 서버로부터 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 상기 클라이언트에 미리 저장된 임계값 초과이면 상기 서버로부터 다음 업데이트 리스트를 수신하고, 상기 경과된 시간이 상기 미리 저장된 임계값 이하이면 상기 캐쉬에 존재하는 데이터를 독출하는 단계, 상기 다음 업데이트 리스트에 상기 데이터가 존재하면, 상기 데이터를 상기 서버에 요청하는 단계를 포함하는 이동망 시스템의 능동적 캐쉬 제어 방법을 제공한다.

상기의 두번째 기술적 과제를 이루기 위하여, 본 발명은 상기의 이동망 시스템의 능동적 캐쉬 제어 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공한다.

상기의 세번째 기술적 과제를 이루기 위하여, 본 발명은 캐쉬를 내장한 클라이언트와 업데이트 리스트를 브로드캐스트 하는 서버를 포함하는 이동망 시스템에 있어서, 상기 서버에 의해 브로드 캐스트되는 데이터 및 상기 서버의 데이터들이 업데이트된 시간에 대한 가중 평균인 업데이트 히스토리를 포함한 업데이트 리스트를 수신하는 클라이언트 수신부, 상기 클라이언트에서 임의의 데이터에 대한 질의가 발생하면, 상기 데이터를 상기 캐쉬에서 검색하는 캐쉬 액세스부, 상기 캐쉬에 상기 데이터가 존재하는 경우, 상기 서버로부터 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 상기 업데이트 히스토리 초과이면 상기 클라이언트 수신부에 의해 다음 업데이트 리스트를 수신하게 하고, 상기 경과된 시간이 상기 업데이트 히스토리 이하이면 상기 캐쉬에 존재하는 데이터를 독출하는 능동적 캐쉬 제어부 및 상기 다음 업데이트 리스트에 상기 데이터가 존재하면, 상기 데이터를 상기 서버에 요청하는 리퀘스트부를 포함하는 캐쉬를 능동적으로 제어하는 이동망 시스템을 제공한다.

본 발명의 한 특징은 불필요한 응답 지연을 제거하는 것이다. 본 발명의 다른 특징은 캐쉬에 있는 데이터를 바로 사용함으로써, 허위경보(false alarm)로 나타나는 불필요한 지연을 제거하는 것이다.

이러한 허위경보(false alarm) 문제 때문에 종래에 사용되는 일관성 모델인 최근값(latest value) 일관성 모델은 빠른 접근 시간을 얻기 위해 적합하지 않다. 일관성 모델은 응용프로그램에 따라 독립적이기 때문에, 본 발명에서는 캐쉬 가용성을 높이기 위해 종래보다 약한 일관성 모델을 사용한다.

본 발명에서는 최근의(latest) IR 일관성을 사용한다. 이 일관성 모델에서 클라이언트는 가장 최근의 IR/UIR에 의해 일관성을 보장 받는다.

종래의 IR/UIR 기반의 알고리즘들에서는 클라이언트는 캐쉬사용을 위해 수동적으로 IR/UIR을 기다리지만, 본 발명에서 제안한 프로토콜에서는 능동적으로 캐쉬를 사용한다.

본 발명은 DCAP(Direct Cache Access Protocol)와 TCAP(Threshold Cache Access Protocol)의 두가지 프로토콜을 제공한다.

DCAP에서는 클라이언트는 자신의 캐쉬에 데이터가 있으면, 다음 IR 또는 UIR까지 기다리지 않고 곧바로 그 데이터를 사용한다.

클라이언트가 곧바로 자신의 캐쉬를 사용했을 때 그 데이터가 최신의 데이터가 아니기 위해서는 첫째, 최근의 IR/UIR까지는 그 데이터가 최신의 데이터여야하고, 둘째, 최근의 IR/UIR 부터 클라이언트의 캐쉬힛이 일어난 시점사이에 업데이트가 일어나야 하며, 셋째, 그 업데이트가 일어난 데이터를 클라이언트가 사용해야만 한다. 세가지 조건이 동시에 일어날 확률은 실제로 매우 적기 때문에, DCAP에서는 캐쉬를 곧바로 사용하더라도 현재성의 손해는 크지 않다.

TCAP에서는 일정한 시간으로 임계값를 정하고 그 시점 이전에는 캐쉬를 곧바로 사용하고 임계값 이후에는 종래의 IR/UIR처럼 다음 IR/UIR을 기다린다. 실제로 오랜 응답지연을 가져오는 임계값 이전의 경우에 캐쉬를 바로 읽음으로써, DCAP와 근사한 응답시간을 가지게 되지만, 위에 설명한 조건 중 두 번째 조건이 임계값에 비례하여 줄어들게 되므로, 현재성의 손해는 이에 비례하여 줄어들 수 있다.

TCAP의 경우 임계값은 클라이언트에 의해 조절될 수 있으며, 임계값이 한 IR/UIR주기일 경우 DCAP와 동일하다. 즉, DCAP는 TCAP의 특수한 경우이다.

이하에서는 도면을 참조하여 본 발명의 바람직한 실시예를 설명하기로 한다. 그러나, 다음에 예시하는 본 발명의 실시예는 여러 가지 다른 형태로 변형될 수 있으며, 본 발명의 범위가 다음에 상술하는 실시예에 한정되는 것은 아니다.

도 4는 IR 기반의 캐쉬 무효화 방법에서 가정하고 있는 시스템 환경을 도식화한 것이다. 본 발명에서도 도 4와 유사한 환경을 가정한다.

서버(400)는 데이터 베이스(DB)를 포함하고, 클라이언트들(410-490)과 통신하기 위한 통신 수단을 포함할 수 있다. 클라이언트들(410-490)은 각각 캐쉬를 포함한다. 서버(400)에서 클라이언트들(410-490)로 정보가 전송될 때에는 브로드 캐스트 채널을 통하고, 클라이언트들(410-490)에서 서버(400)로 정보가 전송될 때에는 온디맨드 채널(On-Demand Channel)을 통한다.

바람직하게는, 임계값은 서버에 의해 소정의 주기마다 브로드 캐스트되는 업데이트 히스토리이거나 클라이언트에 미리 저장된 상수값일 수 있다.

임계값으로 업데이트 히스토리를 사용하는 경우, 업데이트 히스토리는 다음의 수학식 1과 같이 특정 데이터의 최근 업데이트 시간 및 과거 업데이트 히스토리의 가중 평균에 의해 연산된다.

d_h= α*d_h-1+(1-α)*(t_x-T_i)

이때, d_x는 업데이트된 데이터 아이디이고, t_x는 d_x가 업데이트된 시간이며, d_h는 d_x의 업데이트 히스토리이며, d_h-1 은 d_h 이전의 d_x의 과거 업데이트 히스토리이고, T_i는 현재시간을 나타낸다.

α는 과거 업데이트 히스토리를 현재의 업데이트 히스토리에 어느 정도 반영할지를 결정하기 위한 시스템 파라미터로서, 당업자에 의해 임의로 정해질 수 있는 0과 1 사이의 실수값이다.

임계값으로 업데이트 히스토리를 사용하는 경우에는 클라이언트가 적절한 임계값을 서버에 의해 갱신받게 된다.

임계값을 클라이언트에 상수로서 미리 저장하는 경우에는, 당업자가 적절한 값을 정할 수 있다.

이전 업데이트 리스트(IR 또는 UIR)(510, 520)를 수신한 후, 일정한 시간으로 임계값(Vt)를 정하고 그 시점 이전에는 캐쉬를 직접 액세스 하여 데이터를 독출하고, 임계값(Vt) 이후의 시점에는 다음 업데이트 리스트(IR 또는 UIR)(530, 540)을 기다린다.

임계값(Vt) 이전의 경우에 캐쉬를 바로 읽음으로써, 응답시간 지연을 제거하여 DCAP와 근사한 응답시간을 가지게 된다.

이때, 최근의 업데이트 리스트(IR 또는 UIR)(510, 520)를 수신한 시점 부터 클라이언트의 캐쉬 힛(캐쉬 검색)이 일어난 시점 사이에서, 업데이트가 일어나는 경우가 임계값에 비례하여 줄어들게 되므로, 현재성의 손해는 이에 비례하여 줄어들 수 있다.

본 발명의 특징 중 하나인 TCAP 프로토콜은 특정한 기준점을 중심으로 기준점 전에는 캐쉬를 바로 사용하고, 기준점 이후에는 종래의 IR 기반 프로토콜과 동일하게 다음 IR 이후에 캐쉬를 사용한다.

TCAP 프로토콜의 일 실시예를 설명하면, 다음과 같다.

여기서, Q_i = {d_x | d_x 는 T_i이후에 질의된 데이터} 이고, Q_i,k ={d_x | d_x 는 인터벌[T_i,k-1, T_i,k]에 질의된 데이터} 이며, t^c _x는 캐쉬된 데이터아이템 d_x의 타임스탬프이고, T_t는 마지막으로 받은 IR의 타임스탬프이며, T_c는 현재 시간이다.

또한, T_threshold는 임계값의 시간 기준점으로 0 ≤ T_threshold ≤L 의 범위를 갖는다. 도 5의 T_threshold는 임계값(Vt)와 동일한 개념이다.

임계값으로 업데이트 히스토리를 사용하는 경우, 업데이트 히스토리는 수학식 1과 같이 특정 데이터의 최근 업데이트 시간 및 과거 업데이트 히스토리의 가중 평균에 의해 연산된다.

L_data는 사용자가 서버에 요청한 데이터 아이템의 ID 리스트로서, 클라이언트의 요청에 해당한다. t_x는 IR에 포함된 데이터 아이템의 업데이트 시간이고, T_l은 가장 마지막으로 IR을 받은 시점의 타임스탬스(받은시간)이며, T_i는 IR_i를 받은 시점의 타임스탬프(받은 시간)이고, L_bcast는 서버에 의해 사용자에게 방송되는 데이터의 리스트이며, d_x는 데이터 아이템 ID이고, UIR_i,k은 IR_i 와 IR_i+1 사이에서 k번째의 UIR이며, L은 IR의 방송 주기이고, w은 윈도우의 크기(IR은 w주기 만큼의 업데이트 정보를 포함하고 있음)이다.

다음의 표 1은 사용자 C_j 가 IR_i 와 L_bcast를 수신한 경우의 프로토콜을 나타낸다.

if T_l < ( T_i -L*w) then 전체 캐쉬 엔트리를 삭제; for 캐쉬에 있는 각각의 데이터 아이템 < d_x, t^c _x > do if ((d_x,t_x) ∈ IR_i) ∧ (t^c _j < t_x) then d_x를 무효화; for 각각의 데이터 d_x ∈ L_bcast do if (d_x ∈ L_data) then d_x를 클라이언트 로컬 캐쉬에 다운로드; d_x를 최근 질의에 대한 답으로 사용; if d_x 가 무효화된 캐쉬 아이템 then d_x 를 클라이언트의 로컬 캐쉬에 다운로드; T_l = T_i; if (L_data ≠φ) then query(Q_i); L_data≠= φ;

표 1에서 C_j라는 사용자가 인밸리데이션 리포트(Invalidation Report) 와 데이터를 받은 경우, 마지막으로 IR을 받고 L*w 시간 이상 사용자가 IR을 받지 못하면, 전체 캐쉬 엔트리를 삭제한다.

다음, dx가 IR에 포함되어 있고, IR에 있는 dx의 업데이트 시간이 캐쉬에 있는 업데이트 시간보다 크면, dx를 무효화시킨다.

"T_l = T_i;" 의 의미는 현재 받은 IR의 타임스탬프를 가장 마지막으로 받은 IR의 타임스탬프로 설정하는 것이다.

다음의 표 2는 사용자가 UIR_i,k를 수신한 경우의 프로토콜을 나타낸다.

if IR_i를 받지 못함 then break; wait for the next IR; for 캐쉬에 있는 각각의 데이터 아이템 < d_x, t^c _x > do if (d_x ∈ UIR_i,k) then d_x를 무효화; if (L_data ≠φ) then query(Q_i); L_data≠= φ;

다음의 표 3은 클라이언트가 d_x에 대한 질의를 받은 경우의 프로토콜을 나타낸다.

if (T_c-T_t < T_threshold) if d_x가 캐쉬에 있는 유효한 데이터 then 캐쉬에 있는 값을 질의응답을 위해 즉시 사용; else 서버로 d_x 에 대한 질의를 보냄; else L_data = L_data ∪ d_x;

"if (T_c-T_t < T_threshold)"의 의미는 현재시간에서 마지막으로 IR을 받은 시간을 뺀 값이 임계값보다 작을 경우를 나타낸다.

다음의 표 4는 표 1 내지 표 3에 기재된 query(Q)의 프로시져(Procedure)를 나타낸다.

for 각각의 d_x ∈ L_data do L_data 에 대한 질의를 서버로 보냄;

도 6은 발명에 따른 이동망 시스템의 블럭도이다.

클라이언트(610)는 캐쉬 액세스부(612), 캐쉬(613), 능동적 캐쉬 제어부(614), 클라이언트 수신부(615) 및 리퀘스트부(616)를 포함한다.

캐쉬 액세스부(612)는 클라이언트(610)에서 임의의 데이터에 대한 질의(611)가 발생하면, 질의(611)가 발생한 데이터를 캐쉬(613)에서 검색한다.

능동적 캐쉬 제어부(614)는 캐쉬(613)에 질의가 발생한 데이터가 존재하는 경우, 서버(600)로부터 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 임계값 초과이면 클라이언트 수신부(615)에 의해 다음 업데이트 리스트를 수신하게 하게 한다. 이때, 클라이언트(610)는 다음 업데이트 리스트가 수신될때까지 대기한다. 이때, 임계값은 0보다 크고, IR 또는 UIR 주기 보다는 작은 값으로, 당업자에 의해 임의로 정해질 수 있다. 바람직하게는, 업데이트 리스트는 서버(600)에 의해 소정의 주기마다 브로드 캐스트될 수 있다.

임계값으로 업데이트 히스토리를 사용하는 경우, 업데이트 히스토리는 수학식 1과 같이, 특정 데이터의 최근 업데이트 시간 및 과거 업데이트 히스토리의 가중 평균에 의해 연산된다.

이때, 이전 업데이트 리스트는 현재 시점을 기준으로 가장 최근의 업데이트 리스트이고, 다음 업데이트 리스트는 현재 시점을 기준으로 다음 주기에 수신되는 업데이트 리스트이다.

능동적 캐쉬 제어부(614)는 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 임계값 이하이면 캐쉬(613)에 존재하는 데이터를 독출하여 질의(610)에 응답으로 사용한다.

바람직하게는, 능동적 캐쉬 제어부(614)는 다음 업데이트 리스트에 질의(611)가 발생한 데이터가 존재하지 않으면, 캐쉬(613)에 존재하는 데이터를 독출할 수 있다.

클라이언트 수신부(615)는 서버(600)로부터 전송되는 데이터 및 업데이트 리스트를 수신한다.

리퀘스트부(616)는 다음 업데이트 리스트에 질의(611)가 발생한 데이터가 존재하면, 질의(611)가 발생한 데이터를 서버(600)에 요청한다.

바람직하게는, 리퀘스트부(616)는 캐쉬(613)에 질의(611)가 발생한 데이터가 존재하지 않는 경우, 질의(611)가 발생한 데이터를 서버(600)에 요청할 수 있다.

바람직하게는, 서버(600)는 온디맨드 데이터 관리자(601), 브로드 캐스트 관리자(602), 데이터 베이스(603)를 포함할 수 있다. 이때, 온디맨드 데이터 관리자(601)는 리퀘스트부(616)의 요청을 수신한다. 이때, 브로드 캐스트 관리자(602)는 리퀘스트부(616)의 요청에 따라 데이터 베이스(603)를 검색하고, 검색된 데이터를 클라이언트 수신부(615)에 전송한다. 이때, 데이터 베이스(603)는 클라이언트(610)를 위한 복수의 데이터를 저장한다.

캐쉬를 내장한 클라이언트와 서버를 포함하는 이동망 시스템을 가정한다.

서버는 업데이트 리스트를 소정의 주기마다 브로드캐스트하는데, 업데이트 리스트는 수학식 1과 같이 특정 데이터의 최근 업데이트 시간 및 과거 업데이트 히스토리의 가중 평균에 의해 연산된 업데이트 히스토리를 포함할 수 있다.

먼저, 클라이언트에서 임의의 데이터에 대한 질의가 발생하면, 질의가 발생한 데이터를 캐쉬에서 검색한다(710 과정).

다음, 캐쉬에 질의가 발생한 데이터가 존재하는지 판단한다(720 과정).

캐쉬에 질의가 발생한 데이터가 존재하는 경우, 서버로부터 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 임계값 초과이면(730 과정) 서버로부터 다음 업데이트 리스트를 수신하고(740 과정), 경과된 시간이 임계값 이하이면 캐쉬에 존재하는 데이터를 독출한다(760 과정).

한편, 캐쉬에 질의가 발생한 데이터가 존재하지 않는 경우, 질의가 발생한 데이터를 서버에 요청한다(770 과정).

경과된 시간이 임계값 초과하여 서버로부터 다음 업데이트 리스트를 수신한 경우, 다음 업데이트 리스트에 질의가 발생한 데이터가 존재하면(750 과정), 질의가 발생한 데이터를 서버에 요청한다(770 과정).

한편, 다음 업데이트 리스트에 질의가 발생한 데이터가 존재하지 않으면(750 과정), 캐쉬에 존재하는 데이터를 독출한다(760 과정).

바람직하게는, 업데이트 리스트는 서버에 의해 소정의 주기마다 브로드 캐스트될 수 있다.

바람직하게는, 업데이트 리스트는 현재 시간 이전의 특정 데이터에 대한 무효화를 통지하는 인밸리데이션 리포트 또는 업데이티드 인밸리데이션 리포트 중 어느 하나를 포함할 수 있다.

바람직하게는, 서버는 복수의 데이터를 저장하는 데이터 베이스를 포함하고, 클라이언트의 요청에 따라 데이터 베이스를 검색하고, 검색된 데이터를 클라이언트에 전송할 수 있다.

본 발명의 성능을 분석하기 위해 한 개의 서버와 여러 개의 클라이언트가 있는 상황을 가정하여 시뮬레이션을 수행하였다.

데이터의 갱신은 서버에서만 일어나고 데이터에 대한 요청은 클라이언트에서만 일어난다고 가정한다. 그리고, 시뮬레이션을 간편화하기 위해서 데이터의 크기나 대역폭 및 클라이언트가 서버와 연결이 끊어지는 경우는 고려하지 않는다. 시뮬레이션에 사용된 파라미터는 다음의 표 1에 나타난다.

파라미터 (단위)	내용	파라미터 (단위)	내용
Database size (data item)	1000	UIR replicate times	4
Number of clients	100	HOT data items	5% of DB
Broadcast interval (sec)	200	Cold data items	95% of DB
Broadcast bandwidth (bits/sec)	10000	Hot data update probability	33%
Cache size (data item)	1 to 500	Client's zipf parameter	0.95
Broadcast window (broadcast interval)	4	Query generate time (data item)	1 to 200

도 8에서 보여지듯이, 본 발명이 종래의 사용되던 IR/UIR 보다 평균 응답시간이 짧다는 것을 보여준다.

바람직하게는, 임계값은 서버에 의해 브로드캐스트되는 업데이트 히스토리일 수 있다.

바람직하게는, 본 발명의 이동망 시스템의 능동적 캐쉬 제어 방법을 컴퓨터에서 실행시키기 위한 프로그램을 컴퓨터로 읽을 수 있는 기록매체에 기록하여 제공할 수 있다.

본 발명은 소프트웨어를 통해 실행될 수 있다. 소프트웨어로 실행될 때, 본 발명의 구성 수단들은 필요한 작업을 실행하는 코드 세그먼트들이다. 프로그램 또는 코드 세그먼트들은 프로세서 판독 가능 매체에 저장되거나 전송 매체 또는 통신망에서 반송파와 결합된 컴퓨터 데이터 신호에 의하여 전송될 수 있다.

컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 테이터가 저장되는 모든 종류의 기록 장치를 포함한다. 컴퓨터가 읽을 수 있는 기록 장치의 예로는 ROM, RAM, CD-ROM, DVD±ROM, DVD-RAM, 자기 테이프, 플로피 디스크, 하드 디스크(hard disk), 광데이터 저장장치 등이 있다. 또한, 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 장치에 분산되어 분산방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다.

본 발명은 도면에 도시된 일 실시예를 참고로 하여 설명하였으나 이는 예시적인 것에 불과하며 당해 분야에서 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 실시예의 변형이 가능하다는 점을 이해할 것이다. 그러나, 이와 같은 변형은 본 발명의 기술적 보호범위내에 있다고 보아야 한다. 따라서, 본 발명의 진정한 기술적 보호범위는 첨부된 특허청구범위의 기술적 사상에 의해서 정해져야 할 것이다.

상술한 바와 같이, 본 발명에 의하면, 모바일 환경에서 질의가 발생했을 때, 클라이언트들이 자신의 캐쉬를 단시간내에 사용할 수 있게 함으로써, 불필요한 응답 지연시간을 줄이고, 캐쉬내에 요청한 데이터가 존재할 경우 기다리지 않고 바로 질의에 대한 응답을 얻을 수 있기 때문에, 캐쉬 사용률을 높임으로써 캐쉬 가용성을 높일 수 있으며, 허위경보(false alarm) 문제를 제거할 수 있는 효과가 있다.

Claims

캐쉬를 내장한 클라이언트와 업데이트 리스트를 브로드캐스트 하는 서버를 포함하는 이동망 시스템에 있어서,

상기 서버의 데이터들이 업데이트된 시간에 대한 가중 평균인 업데이트 히스토리를 포함한 업데이트 리스트를 수신하는 단계;

상기 클라이언트에서 임의의 데이터에 대한 질의가 발생하면, 상기 데이터를 상기 캐쉬에서 검색하는 단계;

상기 캐쉬에 상기 데이터가 존재하는 경우, 상기 서버로부터 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 상기 업데이트 히스토리 초과이면 상기 서버로부터 다음 업데이트 리스트를 수신하고, 상기 경과된 시간이 상기 업데이트 히스토리 이하이면 상기 캐쉬에 존재하는 데이터를 독출하는 단계; 및

상기 다음 업데이트 리스트에 상기 데이터가 존재하면, 상기 데이터를 상기 서버에 요청하는 단계를 포함하는 이동망 시스템의 능동적 캐쉬 제어 방법.
제 1 항에 있어서,

상기 데이터를 상기 서버에 요청하는 단계는

상기 캐쉬에 상기 데이터가 존재하지 않는 경우, 상기 데이터를 상기 서버에 요청하는 단계를 포함하는 것을 특징으로 하는 이동망 시스템의 능동적 캐쉬 제어 방법.
제 1 항에 있어서,

상기 데이터를 상기 서버에 요청하는 단계는

상기 다음 업데이트 리스트에 상기 데이터가 존재하지 않으면, 상기 캐쉬에 존재하는 데이터를 독출하는 단계를 포함하는 것을 특징으로 하는 이동망 시스템의 능동적 캐쉬 제어 방법.
제 1 항에 있어서,

상기 업데이트 리스트는

상기 서버에 의해 소정의 주기마다 브로드캐스트 되고, 현재 시간 이전의 특정 데이터에 대한 무효화를 통지하는 인밸리데이션 리포트 또는 업데이티드 인밸리데이션 리포트 중 어느 하나를 포함하는 것을 특징으로 하는 이동망 시스템의 능동적 캐쉬 제어 방법.
제 1 항에 있어서,

상기 서버는

복수의 데이터를 저장하는 데이터 베이스를 포함하고, 상기 데이터 베이스에서 특정 데이터의 최근 업데이트 시간 및 과거 업데이트 히스토리의 가중 평균을 연산하여 현재의 업데이트 히스토리를 생성하고, 상기 클라이언트의 요청에 따라 상기 데이터 베이스를 검색하며, 상기 검색된 데이터 및 상기 업데이트 히스토리를 포함한 업데이트 리스트를 소정의 주기마다 브로드 캐스트하는 것을 특징으로 하는 이동망 시스템의 능동적 캐쉬 제어 방법.
캐쉬를 내장한 클라이언트와 업데이트 리스트를 브로드캐스트 하는 서버를 포함하는 이동망 시스템에 있어서,

상기 클라이언트에서 임의의 데이터에 대한 질의가 발생하면, 상기 데이터를 상기 캐쉬에서 검색하는 단계;

상기 캐쉬에 상기 데이터가 존재하는 경우, 상기 서버로부터 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 상기 클라이언트에 미리 저장된 임계값 초과이면 상기 서버로부터 다음 업데이트 리스트를 수신하고, 상기 경과된 시간이 상기 미리 저장된 임계값 이하이면 상기 캐쉬에 존재하는 데이터를 독출하는 단계;

상기 다음 업데이트 리스트에 상기 데이터가 존재하면, 상기 데이터를 상기 서버에 요청하는 단계를 포함하는 이동망 시스템의 능동적 캐쉬 제어 방법.
제 1 항 내지 제 6 항 중 어느 한 항의 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.
캐쉬를 내장한 클라이언트와 업데이트 리스트를 브로드캐스트 하는 서버를 포함하는 이동망 시스템에 있어서,

상기 서버에 의해 브로드 캐스트되는 데이터 및 상기 서버의 데이터들이 업데이트된 시간에 대한 가중 평균인 업데이트 히스토리를 포함한 업데이트 리스트를 수신하는 클라이언트 수신부;

상기 클라이언트에서 임의의 데이터에 대한 질의가 발생하면, 상기 데이터를 상기 캐쉬에서 검색하는 캐쉬 액세스부;

상기 캐쉬에 상기 데이터가 존재하는 경우, 상기 서버로부터 이전 업데이트 리스트를 수신한 시간으로부터 경과된 시간이 상기 업데이트 히스토리 초과이면 상기 클라이언트 수신부에 의해 다음 업데이트 리스트를 수신하게 하고, 상기 경과된 시간이 상기 업데이트 히스토리 이하이면 상기 캐쉬에 존재하는 데이터를 독출하는 능동적 캐쉬 제어부; 및

상기 다음 업데이트 리스트에 상기 데이터가 존재하면, 상기 데이터를 상기 서버에 요청하는 리퀘스트부를 포함하는 캐쉬를 능동적으로 제어하는 이동망 시스템.
제 8 항에 있어서,

상기 리퀘스트부는

상기 캐쉬에 상기 데이터가 존재하지 않는 경우, 상기 데이터를 상기 서버에 요청하는 것을 특징으로 하는 캐쉬를 능동적으로 제어하는 이동망 시스템.
제 8 항에 있어서,

상기 능동적 캐쉬 제어부는

상기 다음 업데이트 리스트에 상기 데이터가 존재하지 않으면, 상기 캐쉬에 존재하는 데이터를 독출하는 것을 특징으로 하는 캐쉬를 능동적으로 제어하는 이동망 시스템.
제 8 항에 있어서,

상기 업데이트 리스트는

상기 서버에 의해 소정의 주기마다 브로드 캐스트 되고, 현재 시간 이전의 특정 데이터에 대한 무효화를 통지하는 인밸리데이션 리포트 또는 업데이티드 인밸리데이션 리포트 중 어느 하나를 포함하는 것을 특징으로 하는 캐쉬를 능동적으로 제어하는 이동망 시스템.
제 8 항에 있어서,

상기 서버는

복수의 데이터를 저장하는 데이터 베이스;

상기 리퀘스트부의 요청을 수신하는 온디맨드 데이터 관리자; 및

상기 데이터 베이스에서 특정 데이터의 최근 업데이트 시간 및 과거 업데이트 히스토리의 가중 평균을 연산하여 현재의 업데이트 히스토리를 생성하고, 상기 리퀘스트부의 요청에 따라 상기 데이터 베이스를 검색하며, 상기 검색된 데이터 및 상기 업데이트 히스토리를 포함한 업데이트 리스트를 소정의 주기마다 브로드 캐스 트하는 브로드 캐스트 관리자를 포함하는 것을 특징으로 하는 캐쉬를 능동적으로 제어하는 이동망 시스템.