모각코 세 번째 모임 개인 계획, 활동과정 및 결과

 * A Dynamic Priority Assignment Technique for Streams with (m, k) - Firm Deadlines를 읽고 작성된 글임.

(https://ieeexplore.ieee.org/document/477249)

A dynamic priority assignment technique for streams with (m, k)-firm deadlines

이번 모각코에서는 (m,k)-Firm의 개념에 대해서 공부할 것이다.

 

---

* 활동과정 및 결과

 

I. INTRODUCTION

Real Time application은 상호 연관이 있는 task들의 연속으로 구성된다.

Task들은 종류별로 Hard, Soft Task가 있는데, Hard의 경우는 해당 Task의 Deadline이 반드시 지켜져야할 때.

Soft는 어느 정도는 Deadline miss가 어느정도 용인가능할 때를 이야기한다.

그러나 이 중간단계가 필요해질 때도 있다.

예를들면 영상의 재생등이 있다. 영상은 연속성이 있는 일련의 데이터들을 나열하며 순서대로 보여줘야한다.

1,2,3,...,n까지의 데이터가 전송된다고 해보자.

지금 사용자가 재생하고 있는 데이터는 1이라 했을 때, n번째 데이터는 Hard deadline을 가질까?

답은 아닐 것이다. 당장 1 다음에 연속적으로 재생될 데이터는 2,3,..일 것이고, n번째 데이터는 어느정도 밀려도 상관이 없다고 볼 수 있다.

반면에, 2와 같이 바로 필요한 데이터는 n번째 데이터에 비해 Priority가 높다고 볼 수 있다.

 

이러한 점에서 도입된 개념이 바로 (m,k)-Firm Deadline이다.

(m,k)-Firm Deadline에서 "Dynamic Failure"란 k개의 연속된 전송에서 Deadline을 만족하는 경우가 m개 미만일 경우이다.

따라서 Stream이 Dynamic failure를 겪는 수치는 QoS가 허용 가능한 수준 이하로 떨어지는 빈도를 나타내는 척도가 될 수 있다. 

Dynamic Failure를 낮추기 위한 우선 순위 할당 방식은 해당 stream에서 Deadline miss가 난 최근 기록을 기반으로 각 노드에게 우선 순위를 할당하는 Distance-based priority(DBP) 방식이 있다.

서버는 이 우선 순위를 Deadline과 같은 다른 매개변수와 함께 사용하여 보류 중인 노드 간의 서비스 순서를 결정한다.

이 DBP 방식은 모든 노드가 동일한 우선 순위 수준을 쓰는 SP 방식보다 Dynamic Failure가 크게 줄어든다.

그러나 정말 이렇게 하면 모든 문제가 없을까?

이 모델의 문제점은 다수의 연속적인 데이터가 Deadline miss가 나는 경우가 더 Critical한 Error라고 볼 수 있으나,

에러의 갯수만 같다면 Loss function을 만족시킬 수 있다는 점이다.

(아까 영상에서 든 예와같이 영상 데이터에서 1,2, [3], 4, [5] 가 손실된 경우와 1,[2],[3],4,5가 손실된 경우는 영상이 딜레이가 되는 정도가 차이가 날 것이다. 그러나 5개중 2개가 오류가 난 경우로 손실 비율은 똑같다.)

 따라서 이러한 부분을 고려하여 (m,k) deadline stream은 k개의 연속적인 전송에 적어도 m개의 필수 데이터가 있는 방식으로 분류하여 Task들을 처리해보자.

---

II. SYSTEM MODEL  AND PROBLEM FORMULATION

Introduction에서 논문의 아이디어의 개략적인 파악이 끝났으면 이제 본격적인 설명을 읽을 차례다.

 

 

해당 논문은 Hard 와 Soft Deadline model의 중간 단계를 정의하며 시작한다.

Real-time customer들의 stream을 생각해보자.

(Customer는 task, message 등 어떠한 schedulable 요소이다.)

Stream의 각 Customer는 처리되기를 기대하는 기간인 Deadline이 존재한다.

만약 모든 Customer가 자신의 deadline 이전에 모든 서비스를 제공받으면, Deadline을 지켰다고 하고,

제공받지 못하면 Deadline miss라고 한다.

논문에서 정의한 (m,k)-Firm은 Stream은 k개의 연속적인 Customer에서 최소 m개의 Customer가 Deadline을 지켜야한다는 가정을 지니게 하는 파라미터 m,k로 특징지어진다.

즉, (m,k)를 통해 Stream에 대해 원하는 QoS를 지정해줄 수 있다.

Stream에서 k개의 연속적인 Customer Window Deadline을 만족하는 Customer가 m개 미만일 때 Dynamic Failure가 발생했다고 한다.

예를 들어, 비디오 스트림의 경우 이러한 파라미터는 원하는 비디오 품질을 지정하며, Dynamic Failure는 비디오 품질이 원하는 품질 아래로 떨어짐을 의미한다.

(1,1)-firm deadlines은 각 스트림의 모든 Customer가 자신의 Deadline을 지켜야한다는 것이다. (Hard deadline)

(1,2)-firm deadlines Stream 두 연속적인 Customer가 Deadline miss가 나면 안된다는 제약을 나타낸다.
(MmMm (O), MmmM(x))

마찬가지로 (4,6)-Firm Deadlines가 있는 Streamd상에서 3개의 연속 Customer가 Deadline이 miss가 나면 안되며 6개의 Customer 중 적어도 4개는 Deadline을 지켜야한다는 것이다.

즉, (m,k)-firm 명세는 miss가 일정한 간격을 지니는 것 외에도  (k-m)/k의 최대 허용 손실률을 의미한다.

예를 들어, (4,5)-firm은 20%의 최대 허용 손실을 의미하고, 조금 더 덜 엄격한 (8,10)-firm 역시 20%의 최대 허용 손실률을 의미한다.

본 논문에서 고려하는 시스템은 Realtime Customer가 있는 N개의 Stream으로 구성되어있다.

이 때, R1,R2...,RN은 각각의 Stream을 나타내며 Rj는 (mj,kj)-firm deadline을 가진다.

이 때, Single server에 대해 Customer들을 일정하게 스케쥴링하여 Dynamic Failure의 평균 확률을 낮추어보자.

 

Dynamic Failure의 확률을 줄이는 가장 간단한 접근 방식은 Customer가 Deadline miss가 날 확률을 줄이는 것이다.

Customer가 Deadline을 놓치는 확률을 줄이면 k개의 연속적인 Customer Window에서 최소 m개의 Customer가 Deadline을 지킬 확률이 증가하기 때문이다.

이것을 구현한 policy들은 대부분 다음과 같이 개략화할 수 있다.

(각 Stream에는 별도의 FIFO queue가 있다.)

Fig.1

 

이러한 Queue는 특정 Stream의 Customer가 도착한 순서대로 서비스를 받게 이루어진다.

개별 스트림 Queue의 맨 앞에 있는 Custoemr가 Service를 받을 후보이며 이중 Service Queue에 들어갈 data Selection은 사용 중인 Policy에 기반한다.

예를 들어, FIFO 정책에서는 Customer arrival time을 기반으로 선택되며 가장 일찍 도착한 Customer가 선택된다.

이러한 Policy는 개별 Customer의 Deadline은 따지지 않는다.

따라서 Deadline까지 고려한 일반적인 정책은 Earlier Dead First(EDF)이다.

이 Policy는 Customer를 Deadline이 빠른 순으로 선택한다.

이렇게 Policy에 따라 Priority를 부여받은 고객들은 우선적으로 처리가 된다. 동일한 Priority의 Customer일 경우 전통적인 방법에서 사용되는 기준 중 임의의 방법을 사용하여 처리한다.

기존의 여러 논문에서는 EDF가 잘 수행된다는 것을 보여주었기 때문에, 이 논문에서도 이 기준을 Policy로 사용한다고

가정한다.

(체코 교환학생 중 수강한 Real-Time System에서 다양한 환경을 가정하고 증명을 직접 해보았는데 이에 관해서는 나중에 포스팅하겠다.)

제안된 체계의 핵심 측면은 Stream Queue의 맨 앞에 있는 Customer에게 Priority가 할당되는 방식이다.

 

여기까지 살펴보고, 시점을 전환하여 Service policy 또한 생각해보자.

일부 Application에서 System은 대기 중인 Customer가 이미 Deadline을 놓친지 여부를 판단할 수 있고,

이러한 Application에서는 이 늦은 고객은 버려질 것이다.

그러나 대기 중인 Customer가 Deadline을 놓쳤는지 여부를 판단할 수 없는 Application의 경우 모든 Customer를 Service해야한다.

따라서 본 논문에서 성능 평가는 이러한 두가지 가능성 모두 고려해서 평가가 될 것이다.

(다음 섹션에서 다루는 내용은 이 두 가지 가능성 중 어떤 것이 채택되었는지는 중요하지 않다.)