Access pointLocal cache server - Wireless Transmission Technology in Multi-point to Multi-point

Backhaul link Access link

분포 함수

𝑃[𝑡]

에 따라서 컨텐츠

𝑓̂

_𝑘

[𝑡] ∈ 𝐹[𝑡]

를 요청한다.

특정 기준값 이상에서는

p

_𝜏,𝑙

[𝑡] = 0

으로 설정하여 컨텐츠마다 최대수명을 다르게 설정할 수 있다.

앞서 기술한 시변 컨텐츠 선호도 확률을 바탕으로 타임슬롯

𝑡

에서의 라 이브러리는

𝐹[t] = {𝑓

_𝜏,𝑙

}

𝜏∈[max(1,𝑡−𝑄+1):𝑡],𝑙∈[1:𝐿]로 주어진다. 또한

𝐹[t]

의 컨텐츠 선 호도 분포 함수는

𝑃[t] = {𝑝

_𝜏,𝑙

[𝑡]}

𝜏∈[max(1,𝑡−𝑄+1):𝑡],𝑙∈[1:𝐿]로 주어진다. 각 사용자가 매 타임슬롯에서 다수개의 컨텐츠를 동시에 요청하는 이벤트를 방지하기 위하여 본 과제는

𝑝

_𝜏,𝑙

[𝑡] ≤

_𝑄𝐿¹ 을 만족하는 컨텐츠 선호도 분포 함수 클래스를 가정한다.

이러한 가정하에

|𝐹[t]| ≤ 𝑄𝐿

이므로

∑

𝜏∈[max(1,𝑡−𝑄+1):𝑡],𝑙∈[1:𝐿]

𝑝

_𝜏,𝑙

[𝑡] ≤ 1

을 만족하 며, 각 사용자는 매 타임슬롯마다 1개 이하의 컨텐츠를 요청하게 된다.

설명의 편의를 위하여, 다음과 같은 가상의 컨텐츠

𝑓

₀를 정의하고 타임 슬롯

𝑡

에서 각 사용자가

𝑓

₀를 요청할 확률을

𝑝

₀

[𝑡]

로 표기한다. 이 때

𝑝

₀

[𝑡]

는 다 음과 같다.

𝑝

₀

[𝑡] = 1 − ∑

^𝑡𝜏=max(1,𝑡−𝑄+1)

∑

^𝐿_𝑙=1

𝑝

_𝜏,𝑙

[𝑡]

(5-2-2)

즉, 각 타임슬롯에서 컨텐츠를 요청하지 않은 사용자는 가상의 컨텐츠

𝑓

₀를 요청하는 사용자로 간주하면, 매 타임슬롯마다 모든 사용자가 하나의 컨텐츠 를 요청하는 모델로 해석한다. 그러므로 타임슬롯

𝑡

에서 사용자

𝑘

는 컨텐츠

𝑓̂

_𝑘

[𝑡] ∈ 𝐹[𝑡] ∪ {𝑓

₀

}

를 다음과 같은 확률로 요청한다.

Pr(𝑓̂

𝑘

[𝑡] = 𝑓

_𝜏,𝑙

) = 𝑝

_𝜏,𝑙

[𝑡]

for

𝜏 ∈ [max(1, 𝑡 − 𝑄 + 1): 𝑡], 𝑙 ∈ [1: 𝐿]

(5-2-3)

Pr(𝑓̂

𝑘

[𝑡] = 𝑓

₀

) = 𝑝

₀

[𝑡]

(5-2-4)

다. 캐시 서버 업데이트, 캐싱 적중 확률

본 과제는 엑세스포인트가 자신의 캐시 서버를 매

𝑇

타임슬롯마다 주 기적으로 업데이트 함을 가정한다. 구체적으로, 타임슬롯

𝑡 = (i − 1)T + 1

에서 엑

세스포인트는 과거의 사용자 컨텐츠 요청 정보, 즉

{𝑓 ̂ [𝑡

_𝑘 ^′

]}

_𝑡_′∈[1:𝑡−1],𝑘∈[1:𝐾]에 기반 하여 캐시 서버의

𝐶[𝑡] ∈ 𝐹[𝑡 − 1]

을 업데이트 한다. 여기서

i ∈ {1,2, ⋯ }

이다. 캐 시 서버 업데이트 후 타임슬롯

𝑡 ∈ [(𝑖 − 1)𝑇 + 1, ⋯ , 𝑖𝑇]

동안 캐시 서버를 그대로 유지하면서 사용자 요청에 대해 서비스한다. 이 같은 업데이트 방법에 의하여 다 음이 성립한다.

𝐶[1] = 𝐶[2] = ⋯ 𝐶[𝑇] = ∅

(5-2-5)

𝐶[𝑇 + 1] = 𝐶[𝑇 + 2] = ⋯ 𝐶[2𝑇] ⊆ 𝐹[𝑇]

(5-2-6)

⋮

(5-2-7)

𝐶[𝑖𝑇 + 1] = 𝐶[𝑖𝑇 + 2] = ⋯ 𝐶[(𝑖 + 1)𝑇] ⊆ 𝐹[𝑖𝑇]

(5-2-8) 따라서 타임슬롯

𝑡

에서의 캐싱 적중 확률(각 사용자의 요청 컨텐츠가 캐시 서버에 저장되어 있을 확률)은 다음과 같이 표현된다.

𝑝

_ℎ𝑖𝑡

[𝑡] = ∑

^𝑡𝜏=max(1,𝑡−𝑄+1)

∑

^𝐿_𝑙=1

𝑝

_𝜏,𝑙

[𝑡] 1(𝑓

_𝜏,𝑙

∈ 𝐶[𝑡])

(5-2-9)

여기서

1(∙)

는 Indicator 함수를 의미한다. 본 과제는 다음과 같이 표현 되는 평균 적중 확률을 최대화하는 캐싱 기법에 대해 연구하고자 한다.

𝑝

_𝑎𝑣𝑒

= lim

𝑇′→∞

𝑇′

∑

^𝑇′_𝑡=1

𝑝

_ℎ𝑖𝑡

[𝑡]

(5-2-10)

4. 제안 기법

본 장은 제안 기법에 대해 소개한다. 먼저 시변 컨텐츠 선호도 분포 함 수 추정 기법에 대해 소개하고, 이를 활용한 캐시 서버 업데이트 기법에 대해 소 개한다.

가. 시변 컨텐츠 선호도 분포 함수 추정

본 절에서는 시변 컨텐츠 선호도 분포 함수 추정 기법에 대해 제안한다.

먼저 현재 타임슬롯을

𝑡

₀라고 표기하고

𝑡

₀

≥ 𝑄 + 1

을 만족한다고 가정한다. 따라 서 현재 타임슬롯을 기준으로 이미 컨텐츠 수명이 종료된 컨텐츠 집합은

{𝑓

_𝜏,𝑙

}

_{𝜏∈[1:𝑡}

0−𝑄],𝑙∈[1:𝐿]와 같다. 먼저

𝑡 ∈ [𝜏: 𝜏 + 𝑄 − 1]

에 대해, 선호도 확률

𝑝

_𝜏,𝑙

[𝑡]

를 다음의 히스토그램으로 대체한다.

𝑝̂

_𝜏,𝑙

[𝑡] =

_𝐾¹

∑

^𝐾_𝑘=1

1(𝑓 ̂ [𝑡] = 𝑓

_𝑘 _𝜏,𝑙

)

(5-2-11)

다음으로

𝑡

_𝜏,𝑙를 모든

𝑡 ∈ [𝑡

_𝜏,𝑙

+ 1: 𝜏 + 𝑄 − 1]

^{에 대해}

𝑝̂

_𝜏,𝑙

[𝑡] = 0

^{을 만족} 하는

[𝜏: 𝜏 + 𝑄 − 1]

범위의 값 중 최솟값으로 정의한다. 이와 같은 조건을 만족하 는 값이

[𝜏: 𝜏 + 𝑄 − 1]

범위에 없는 경우

𝑡

_𝜏,𝑙

= 𝜏 + 𝑄 − 1

으로 설정한다.

또한

𝑝̂

_𝜏,𝑙

[𝑡]

를 Interpolation을 하여 획득한 연속 함수를

𝑝̃

_𝜏,𝑙

(𝑡)

^{로 정의} 한다. 이 때

𝑡 ∈ [𝜏, 𝜏 + 𝑄 − 1]

과 같다. 이를 바탕으로 다음과 같은 연속 함수를 정 의한다.

𝑝̇

_𝜏,𝑙

(𝑡) = 𝑝̃

_𝜏,𝑙

(

^𝑡^𝜏,𝑙^−𝜏

𝑄−1

𝑡 + 𝜏)

(5-2-12)

이 때

𝑡 ∈ [0, 𝑄 − 1]

과 같다. 수식 (5-2-11), (5-2-12)로부터

𝑝̇

_𝜏,𝑙

(0) = 𝑝̂

_𝜏,𝑙

[𝜏]

와

𝑝̇

_𝜏,𝑙

(𝑄 − 1) = 𝑝̂

_𝜏,𝑙

[𝑡

_𝜏,𝑙

]

관계가 성립함을 알 수 있다.

{𝑓 ̂ [𝑡

_𝑘 ^′

]}

_𝑡_′∈[1:𝑡−1],𝑘∈[1:𝐾]로부터 시변 컨텐츠 선호도 분포 함수를 대표하 는 함수를 추출하기 위하여 파라미터

𝑐

_𝜏,𝑙 (이 때

𝜏 ∈ [1: 𝑡 − 𝑄 + 1], 𝑙 ∈ [1: 𝐿]

의 범 위로 주어짐)로 표현되는 다음 함수를 도입한다.

𝑝

_{𝑡𝑦𝑝𝑖𝑐𝑎𝑙}

(𝑡) = ∑

^𝑡_𝜏=1⁰^−𝑄

∑

^𝐿_𝑙=1

𝑐

_𝜏,𝑙

𝑝̇

_𝜏,𝑙

(𝑡)

(5-2-13)

이 때

𝑡 ∈ [0, 𝑄 − 1]

과 같다. 위 함수로에서 파라미터

𝑐

_𝜏,𝑙은 다음의 최 적화 문제의 해로 주어진다.

arg min

문서에서 Wireless Transmission Technology in Multi-point to Multi-point Comunications (페이지 195-200)