A Resource Allocation Model for QoS Management

느낀점

 

 

 

Problem Statement

Q-RAM(QoS 기반 자원 할당 모델)이 다루는 근본적인 문제(Fundamental Problem)는 동시에 실행되고 동일한 자원 유형을 놓고 경쟁하는(Run Concurrently and Contend for the same resource types) 여러 애플리케이션에 자원을 할당하는(Allocate Resources)것이다. 이러한 애플리케이션은 타이밍, 신뢰성, 보안 제약 조건은 물론 애플리케이션 별 품질 요구사항을 만족해야 한다.

Q-RAM은 특히 다음과 같은 시스템 요구사항을 충족하기 위해 자원을 할당하는 분석 모델로 제시된다.

• Timeliness, Reliable Delivery Schemes, Cryptographbic Security, Data Quality 같은 Multiple QoS Dimensions에 걸친 동시 요구사항 충족
• 애플리케이션이 요구 사항을 충족히가 위해 처리 주기, 메모리, 네트워크 대역폭, 디스크 대역폭 등 여러 자원 유형에 동시에 접근해야 하는 경우

이 모델의 목표는 각 애플리케이션이 최소한의 요구사항을 충족할 수 있다는 제약 하에 전체 시스템 유틸리티를 최대화하도록 자원을 할당하는 것이다.

이 문제의 중요성은 국방 시스템, 주문형 서비스 및 인터넷 연결 시스템과 같은 대규모 분산 시스템에서 다양한 요구 사항을 만족시키기 위해 애플리케이션에 충분한 자원을 할당하는 것이 근본적인 문제이기 때문이다. Q-RAM과 같은 성능 중심의 자원 할당을 위한 기본적이면서도 유연한 모델은 적절한 절충안을 만드는데 유용하다. 기존의 많은 자원 할당 연구는 단일 시간 공유 자원에 초점을 맞추었으며, 타임리스, 보안 및 신뢰할 수 있는 데이터 전송과 같은 요구 사항을 동일한 맥락에서 다루거나 서로 절충하는 작업은 거의 이루어지지 않았습니다. 따라서 Q-RAM은 이러한 다차원 QoS 요구 사항과 다중 자원에 대한 동시 접근 문제를 해결하려는 중요한 첫걸음이다. 이 모델은 자원 프로파일과 애플리케이션 유틸리티 함수를 식별함으로써 효율적이고 실시간으로 자원 할당 결정을 내리는데 도움이 될 수 있다. 

 

실시간 및 분산 시스템에서는 여러 응용 프로그램이 동시에 여러 자원(CPU, 메모리 등)에 접근해야 하며, 이때 QoS(서비스 품질) 측면에서도 다양한 요구사항(예: 시간 제약, 보안, 신뢰성, 데이터 품질)을 만족해야 한다.

하지만, 시스템 자원은 한정되어 있기 때문에, 각 애플리케이션이 요구하는 최소한의 자원을 보장하면서도 시스템 전체의 유틸리티(서비스 가치)를 극대화하는 자원 할당 방법이 필요하다.

 

Contributions

1. Q-RAM 모델 제안: 다차원 QoS를 고려하는 일반적인 자원 할당 프레임워크
2. 애플리케이션 별로 유틸리티 함수를 정의하여 자원 할당의 효과를 수치화
3. 단일 자원 및 단일/다중 QoS 차원을 고려한 최적 및 근사 할당 알고리즘 제시
4. 실 예로 RT-Phone(비디오 컨퍼런싱 시스템)을 통해 모델 적용 설명

 

Key Ideas

• QoS 차원: 시간 제약, 보안(암호화), 신뢰성, 데이터 품질 등
• 유틸리티 함수: 자원을 얼마나 할당받았는지에 따라 애플리케이션이 얼마나 성능이 향상되었는지를 수치화
• 목표: 모든 애플리케이션이 최소 자원을 확보하면서, 시스템 전체 유틸리티의 합을 극대화
• Min-Linear-Max 함수: 단순하고 효율적인 유틸리티 함수 구조
• 다차원 QoS -> 단일 함수로 변환: 계산 효율성을 위한 구조 단순화
• 이산적 QoS 수준(예: 암호화 옵션) 도 수학적으로 다룸

 

Mathematical Views

Theorem 1: 단일 자원, 단일 QoS 차원

최적 자원 할당의 필요 조건은 다음과 같다
$$\forall i:R_i=0 \,\,\, or \,\,\, U_i^{'}(R_i)=U_j^{'}(R_j)\,\,\,\,(R_i,R_j>0)$$

증명:

• 어떤 애플리케이션 $i$의 한계 유틸리티 $U_i^{'}$가 $j$보다 크다면, 자원을 $j$에서 $i$로 아주 조금 옮기면 시스템 유틸리티가 증가 -> 기존 할당이 최적이 아님 -> 모순
• 따라서 모든 활성 애플리케이션은 동일한 한계 유틸리티를 가져야 함

직관:

• 자원을 가장 가치 있는 쓸 수 있는 곳에 먼저 할당하라

 

Corollary (Min-Linear-Max 유틸리티 함수)

정의:
$$U_i(R_i)=\left\{\begin{matrix} 0 \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,R_i<R_i^{min}\\s_i\cdot(R_i-R_i^{min})\,\,\,\,\,\,\,\,\,R_i^{min}\leq R_i\leq R_i^{max} \\Fix\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, R_i>R_i^{max} \end{matrix}\right.$$

필요 조건:

• $R_i = 0$, 또는 $R_i = R_i^{max}$, 또는 모든 활성 애플리케이션은 동일한 기울기(Slope)를 갖는다.

직관:

• 가성비 좋은 애플리케이션부터 자원을 할당하고, 최대치를 넘으면 멈춘다.

 

최적 자원 할당 알고리즘 (단일 자원)

1. 모든 애플리케이션에 최소 자원을 먼저 할당
2. 남은 자원을 보면서 가장 높은 $U_i^{'}(R_i)$를 갖는 집합을 찾음
3. 그 집합 내에서 자원을 동일하게 늘려가며 U_i^{'}가 같아질 때까지 할당
4. 자원이 다 떨어질 때까지 반복

직관:

• 가장 급한 목마른 사람에게 물을 먼저 주는 "물 붓기" 전략

 

다차원 QoS -> 단일 함수로 변환

1. QoS 차원별 자원 소비 함수와 유틸리티 함수 생성
2. 자원 예산을 기준으로 등고선을 생성하고 유틸리티 맵에 투영
3. 각 자원 수준마다 최대 유틸리티를 뽑아 단일 함수로 변환

직관:

• 다차원 문제를 1차원으로 줄이면 계산이 훨씬 쉬워진다.

 

의존적인 이산 QoS (예: 암호화)

• 예: 암호화를 하면 유틸리티 증가량은 $A$, 자원 소모는 $r_e\cdotR$로 증가
• 암호화 유틸리티는 비암호화 유틸리티보다 시작점이 오른쪽, 기울기는 더 작음
• 결과: 암호화 여부는 자원 여유가 있을 때만 선택됨

직관:

• 암호화는 사치다. 여유 있을 때만 사용

 

 

REF

R. Rajkumar, C. Lee, J. Lehoczky, and D. Siewiorek, “A Resource Allocation Model for QoS Management,” in Proc. 18th IEEE Real-Time Systems Symposium (RTSS), 1997, pp. 298–307. DOI: 10.1109/REAL.1997.641297