Project Kick-Off ** IEEE 802.16 m *** Femto Cell **** Smart BS

Report
Virtual Appliance Content Distribution
for Global Infrastructure Cloud Service
Mobile and Pervasive Computing Reading Group
2011. 06. 08
신승재
한국과학기술원 전산학과
순서
• Document Information
• Virtual Appliance Service in Cloud System
• Problem Definition: Stage Scheduling of VA Content
• Scheduling for the Continuous Model
• Scheduling for the Integral Model
• Algorithm Performance Summary
• Simulation Results
• Conclusion and Discussion
2
Document Information
• 논문 정보
문헌정보: INFOCOM 2010
저자정보: Amir Epstein, Dean H. Lorenz, Ezra Silvera, and Inbar Shapira (IBM Haifa Research Lab, Israel)
내용
본 논문은 Global Infrastructure Cloud 시스템 상에서 동작하는 Virtual Appliance (VA) Service의 Stage Scheduling
문제를 다루고 있다. Virtual Appliance Service는 stage 라고 불리는 거대한 메모리에 Appliance Image를 load하고
사용자가 stage에 접속하여 해당 Image를 자신의 local memory로 다시 복사해 가는 방식으로 동작한다. 따라서 한정
된 용량의 stage로 가능하면 많은 고객에게 VA Service를 제공할 수 있는 stage scheduling이 중요한 문제로 작용하
게 된다. 저자들은 Appliance Image의 stage scheduling 문제를 maximum weighted job scheduling 문제의 형태로
정의하고 total weight 값 측면에서 sub-optimal performance를 얻을 수 있는 스케줄링 알고리즘을 제안하고 있다.
3
Virtual Appliance Service in Cloud System
Cloud 컴퓨팅 개념을 도입한 구글의 크롬북
출처: http://en.wikipedia.org/wiki/Cloud_computing
Cloud Computing
- 네트워크를 통해 연결된 여러 개의 컴퓨팅 기기가 지닌 HW/SW 리소스들을 cloud라고 불리는 시스템으로 추상화
하여 공유하는 기술
- Cloud에서 말하는 리소스는 CPU, Memory와 같은 primitive HW 리소스가 될 수도 있고, application 및 SW와
같은 high-level 리소스가 될 수 도 있다.
- Vision: 사용자는 단지 cloud에 접속하는 것으로 원하는 모든 종류의 computing activity를 수행할 수 있다.
- 예: 워드 프로세서를 설치해서 사용하는 것이 아니라 “접속해서 사용”한다.
4
Virtual Appliance Service in Cloud System
VA Users
Local
Environment1
(Local Cloud
Space)
Local
Environment2
Local
Environment3
Stage Environment
(Shared Cloud Space)
VA Content (Image) Provider
Entry
Point
Global Infrastructure Cloud
Virtual Appliance (VA) Service in Global Infrastructure Cloud System
- 모니터, screen, 키 패드 등 입출력 장치를 갖춘 generic HW device에 상황에 따라 필요한 appliance SW Image를
load하여 사용 (즉 사용자가 지닌 generic device가 상황에 따라 여러 가지 appliance로 동작하도록 함)
- 예: 사용하는 SW Image에 따라 사용자 디바이스는 범용 노트북이 될 수도 있고, navigation 기기가 될 수도 있으며,
MP3 플레이어가 될 수도 있다.
- Appliance Image는 load 되면 바로 사용할 수 있도록 pre-configure 되어 있다 (Turn-Key Solution)
- 따라서 VA content provider 들은 기성품과 같이 사전에 최적의 Appliance Image를 만들어 놓고 필요할 때 마다
사용자의 cloud memory space로 복사하는 과정을 거치게 된다.
- 하나의 Appliance Image는 수 GB ~ 수십 GB 용량이 될 것으로 예상됨
5
Problem Definition: Stage Scheduling of VA Content
본 연구의 목표: Deployment Order Scheduling of VA Content in Bounded Stage Memory
- 한정된 용량의 stage environment에서 가능하면 total cost를 최대화 할 수 있는 서비스를 제공할 수 있도록 VA
Content의 deployment order를 결정한다.
Notations and Assumptions
-
: Stage Memory의 용량
-
: VA request의 개수
-
: VA Image
의 용량
-
: VA Image
의 deployment due date
- Due date 이전까지 load가 완료되어야 하며 그렇지 못한 VA request는 실패한다.
- Load가 완료된 VA Image는 due date
까지 메모리를 점유하고 있다가 local environment로 즉시 복사된다.
-
: VA Image
의 weight 값 (cost = 사용자의 지불 가격)
-
: VA Image
의 loading time (entry point를 통해서 image를 memory에 load하는데 걸리는 시간)
- Loading time
은
- 본 논문에서는
에 비례한다. 즉
로 가정함, 즉
- VA Image의 load는 parallel하게 이루어질 수 없음
- VA Image
-이때
가 시간
부터
에 loading을 시작하면
에서
완료한다.
까지의 VA Image의 stage holding interval을
- 또한 VA Image의 loading interval을
로 표시한다.
로 표시한다.
6
Problem Definition: Stage Scheduling of VA Content
Schedule
- Job (VA request instance) 의 집합
Load of Schedule = Used Capacity of Stage Memory: 시간 t에서 schedule S가 점유하고 있는 용량
Weight of Schedule = Total Cost of Schedule
- 즉 연구의 목표는 total weight이 가장 높도록 스케줄을 결정하는 것이다.
7
Problem Definition: Stage Scheduling of VA Content
Stage Scheduling은 VA Image의 loading 방식에 따라서 접근 방법이 달라짐
- 따라서 저자들은 VA Image의 loading 방식을 두 가지 모델로 나눔
1. Continuous Model
- Loading 과정에서 stage의 점유 용량이 시간에 따라 연속적으로 proportional 하게 증가함
- 만일 VA Image
의
가 5이고
- 따라서 시간 13부터는 VA Image
가 8 이라면 시간 7에서
의 stage 점유 용량은 2가 됨
는 자신의 용량 8만큼을 점유한 상태로 due date 까지 stage에 머물게 된다.
1. Continuous Model의
-
에 의해 다음의 식을 만족함
8
Problem Definition: Stage Scheduling of VA Content
Stage Scheduling은 VA Image의 loading 방식에 따라서 접근 방법이 달라짐 (cont’d)
- 따라서 저자들은 VA Image의 loading 방식을 두 가지 모델로 나눔
2. Integral Model
- Loading 과정에서 VA Image의 용량 전체를 reserve, 즉 loading 과정에서 점진적으로 용량이 증가하는 것이
아니라 용량이 바로 증가함
- 만일 VA Image
의
가 5이고
가 8 이라면 시간 5에서
의 stage 점유용량은 8로 시작함
2. Integral Model의
-
에 의해 다음의 식을 만족함
따라서 Continuous Model에 비해서는 Integral
Model의 스케줄링이 더 어려움 → 따라서 저자들은
Continuous Model의 스케줄링 기법을 먼저 제안하
고 그로부터 Integral Model 스케줄링 기법을 도출
하고 있다.
9
Scheduling for Continuous Model
Right-Tight Schedule 이 란 어 떤 job (VA image) 의
loading이 끝나면 바로 다른 job의 loading을 시작하는
것을 말함
Right-Tight Scheduling의 예
Continuous Model에서 right-tight schedule S의 load는 다음과 같이 계산됨
-
로 인해 스케줄 S의 time – capacity 그래프가 기울기가 1인 직선으로 증가하는 것에서 기인함
10
Scheduling for Continuous Model
임의의 feasible한 schedule (stage capacity를 넘지 않는)
로부터 무조건 right-tight schedule을 만들 수 있다.
Right-tight 스케줄을 만드는 이유는 고정된 시간 내에 되도록
많은 job을 stage에 loading 시키기 위한 것이다.
따라서 un-weighted VA model에서는 right-tight scheduling은
optimal이다 (obvious!!)
Idea Of Proof
- 임의의 feasible schedule로부터 right-tight schedule을 만드는 알고리즘이 있음을 보이면 된다.
Right-Tight Schedule 변환 알고리즘
1. 임의의 feasible schedule에서 due date가 가장 큰 순서대로 job을 정렬한다.
2. 첫 번째 job (due date가 가장 큰 job)은 loading time이 자신의 due date에 맞춰지도록 right shift 시킨다.
3. 이후에 나타나는 job들에 대해서는 loading time이 자신의 due date 또는 자신의 이전 job의 loading 시작 시간에
끝나도록 한다.
4. 즉 이전 job의 loading이 끝나는 시점에서 다음 job의 loading이 바로 이루어지도록 shift 시키면 된다.
11
Scheduling for Continuous Model
Earliest Due Date order: S에 속한 각 job의 due date이
non-decreasing order로 스케줄 된 것을 말한다.
결론부터 말하면 이 Lemma는 right-tight schedule에 EDD order를
지 닌 optimal weight schedule 이 반 드 시 존 재 한 다 는 것 을
설명하고 있다.
Idea Of Proof
- Proof By Contradiction: EDD order가 아닌 right-tight optimal schedule S를 가정하고 그것의 property를 분석
하고 모순을 찾아낸다.
- EDD order가 아닌 right schedule은 중간에 due date이 decreasing order인 job sequence를 포함하게 된다.
이것을 inversion 이라고 부르자.
- 그렇다면 이후에 inversion이 있는 원래 schedule S에서 이 inversion들을 non-decreasing order로 다시 바꾼
새로운 schedule S’을 제안하면 inversion 횟수가 다시 줄어들게 된다.
- 그런데 이때 S’ 역시 right-tight라는 특성을 만족하기 때문에 S와 S’ 사이에는 다음의 식이 만족한다.
- 결국 위의 식에 의해 유한 개의 inversion을 계속 없에면 optimal weight을 가진 EDD order schedule을 얻을 수
있다.
12
Scheduling for Continuous Model
Continuous Deployment Model에서 optimal stage schedule의 두 가지 특징
1. Right-tight schedule이다. 다시 말해 entry point의 loading 작업이 가능하면 끊기지 않고 계속된다.
2. Non-decreasing EDD (Earliest Due Date) order의 순서로 job schedule을 만들면 된다.
일단 입력 job의 set을 Non-decreasing order로 정렬한다
주어진 모든 job을 무사히 schedule 하는 것이 가능할 경우
스케줄의 total weight는 W가 될 것이다.
f(j, w)는 {1, …, j} 까지의 job에 대해 total weight가 w인
schedule할 수 있는 maximum time: 이것을 구한다는 것은
1부터 j까지의 job에 대해 total weight가 w인 right-tight
schedule을 구한다는 것이 된다.
여기서 loading time이 마치는 시간을 이전 job의 scheduling
시작 시간 또는 자신의 due date에 맞춘다. 즉 Lemma 1에서
소개한 right-tight 스케줄 property를 만족시키는 statement
결국 최종적으로 계산되는
와
가 각 job의 stage schedule이 될 것임
Continuous Deployment의 optimal scheduling 알고리즘
13
Scheduling for Continuous Model
Lemma 4.3의 의의
- 주어진 optimal scheduling 알고리즘이 어떠한 w에 대해서도 right-tight scheduling property를 만족한다는 것
- 증명은 j에 대한 induction을 통해 얻을 수 있으나 자세한 사항은 생략함
Theorem 4.2와 Corollary 4.1은 알고리즘의 구조를 살펴보면 자명함
- General case(weighted job scheduling)의 경우 n X W의 중첩 loop로 돌아감
- un-weighted case인 경우 W가 n이 되므로 O(n^2) complexity가 자명
W가 매우 큰 경우 Optimal Scheduling 알고리즘의 복잡도가 너무 커짐 → 따라서 optimality를 다소 포기하는 대신
알고리즘의 complexity를 줄이는 FPTAS (Fully Polynomial Time Approximation Scheme) 변환이 필요
14
Scheduling for Continuous Model
Idea of Proof
- 주어진 Optimal Scheduling 알고리즘의 parameter를 scale하면
의 복잡도로 동작한다는 것을 보인다.
- 먼저 주어진 job들의 각 weight를 훨씬 작은 수로 scale down
- Scale down 된 weight parameter를 가지고 알고리즘 1을 수행하면 S’이라는 스케줄을 얻는다.
- 이 때 optimal Schedule과 S’ 사이에는 다음의 관계를 만족한다.
- 상기 부등식에 의하여
where
- 결국
- 이것은
- 따라서 위와 같은 scaling down 방식을
approximation이라고 한다. 그 이유는 optimal schedule S의
weight가 S’의 weight의
정도로 높기 때문이다.
- 즉 FPTAS는 optimality를
만큼 낮추는 대신 알고리즘의 complexity를 poly time level로 낮추는 효과가 있다.
다음 목표는 Integral Model에서의 stage scheduling을 구하는 것이다.
15
Scheduling for Integral Model
Integral Model의 Scheduling 접근 방법
- Integral Model은 시간에 따른 stage 용량의 가용성이 Continuous Model에 비해 떨어지기 때문에 scheduling이 더
어렵다.
- 저자들의 접근 방법: Continuous Model에서 산출한 optimal schedule에서 Integral Model Assumption을 적용한
후 feasibility를 깨는 job 들을 제거하는 방식으로 새로운 schedule을 산출함
Integral Model의 4가지 Sub-case
1. General Case (Arbitrary Sized Jobs): Job (VA Image)의 size에 제한이 없으며, weighted case와 un-weighted
case의 두 가지 경우로 나눈다.
2. Unit-Sized Job Case: Job size가 fixed 되어 있는 경우에는 continuous model에서 사용했던 FPTAS 알고리즘을
그대로 사용 가능함
3. Small Sized Job Case: Job size가 작은 경우에는 제거해야 하는 job의 양이 매우 작기 때문에 거의 sub-optimal
weighted schedule을 얻을 수 있다.
4. Large Sized Job Case:
16
Scheduling for Integral Model
General Case (Un-weighted Job Case)
- Continuous Model에서 optimal schedule S를 구하고 S가 Integral Model에 적용되었을 경우에 unfeasibility를 유발
하는 Job을 골라내는 방법으로 새로운 스케줄 S’을 construct 한다.
Idea of Proof
- Continuous Model에서 얻어진 optimal schedule S에서 total weight가 optimal weight의 ½ 이상인 스케줄 S’
을 산출하는 알고리즘이 있음을 보인다.
Algorithm
1. S에 integral model assumption을 적용하고 시간 축을 따라 좌에서 우로 (작은 쪽에서 큰 쪽으로) 이동하면서
VA Image의 총량이 stage의 capacity를 초과하는 시간 구간을 찾는다.
2. Capacity 용량이 초과하는 구간 마다 가장 처음 capacity를 초과하는 job을 discard 한다. (해당 job은 스케줄에
실패한 것으로 간주함)
3. 1 ~ 2의 과정을 반복하면 worst case인 경우 두 개의 job schedule 당 1개 꼴로 capacity 초과가 발생한다.
따라서 최대 절반의 job을 discard 하면 capacity 초과가 절대 발생하지 않는다.
17
Scheduling for Integral Model
General Case (Weighted Job Case)
- Un-weighted case와 동일한 접근 방식을 따른다.
Idea of Proof
- Un-weighted case와 동일한 접근 방식이다. Continuous Model에서의 optimal schedule S에서 새로운 스케줄 S*
를 construct 할 수 있는 알고리즘이 있음을 보인다.
Algorithm
1. S에 integral model assumption을 적용하고 시간 축을 따라 우에서 좌로 (큰 쪽에서 작은 쪽으로) 이동하면서 VA
Image의 총량이 stage의 capacity를 초과하는 시간 구간을 찾는다.
2. Capacity 용량이 초과하는 구간 마다 가장 처음 capacity를 초과하는 job을 discard 한다. (해당 job은 스케줄에
실패한 것으로 간주함)
3. 1 ~ 2의 과정을 반복하면 un-weighted job case와 마찬가지로 모든 시간 축에서 job capacity 용량의 초과 구간이
모두 제거된 새로운 스케줄 S’이 산출된다. 하지만 weighted case이기 때문에 이 결과만 가지고는
조건을 보장할 수 없다.
4. 그런데 3의 경우에서 반대로 제거된 job들을 모은 스케줄 S’’도 시간 축에서 보았을 때 용량 추가 구간이 없다는 것
을 보일 수 있다. (S’ U S’’ = S). 따라서 S’과 S’’ 모두 feasible 하기 때문에 둘 중에 total weighted 용량이 큰 것을 S*
으로 고르도록 함으로써
조건을 만족시킬 수 있다.
18
Scheduling for Integral Model
Unit Job Sized Case
- 이 경우는 continuous model을 시간 상에서 discrete approximation 시킨 경우와 비슷하기 때문에 continuous case
알고리즘을 그대로 적용할 수 있다.
이 부분의 조건을
로 전환하면 된다.
19
Scheduling for Integral Model
Small Sized Job Case
- 이 경우도 continuous model의 optimal schedule S에서 discarding을 통해 목표에 맞는 새로운 스케줄 S’을 산출하는
알고리즘이 존재한다는 것을 보인다.
20
Scheduling for Integral Model
Small Sized Job Case의 중요성
- Small job의 경우 continuous model의 optimal schedule에서의 discard ratio가 작다. 따라서 아래와 같은 유용한
성질들을 지닐 수 있다.
21
Scheduling for Integral Model
Large Job Case
- Algorithm 1과 같은 dynamic programming style로 optimal schedule을 찾을 수 있는데 동작하는데, 주목할 만한 점
은 Algorithm 1은 시간 축 상으로 큰 쪽에서 작은 쪽으로 shift 하면서 schedule을 찾는데 이 경우는 반대로 shift 하며
수행된다는 점이 다르다.
22
Scheduling for Integral Model
Summary
- 저자들은 integral loading이 realistic 하지만, optimal schedule을 찾기가 어렵기 때문에 해석이 용이한 continuous
loading 시나리오에서 먼저 optimal schedule을 찾고 이후에 integral model을 위한 sub-optimal schedule을 derive
하는 framework을 제안하고 있다.
23
Simulation Results
Integral Deployment Model을 가정하고 시뮬레이션을 통해 VA image의 deployment 과정을 실험
- 369개의 Job (VA request)을 Poisson process 형태로 발생시킴
- 각 VA Image의 size는 3GB, 10GB 및 30GB 중에서 uniformly selected
- Memory loading rate은 1GB/s 이며 각 request의 weight는 모두 1로 동일함
- 제안하는 알고리즘 가운데 2-approximation FPTAS 알고리즘을 well-known EDD (Early Due Date) heuristic
알고리즘과 비교: due date까지 deployment에 성공한 VA request의 개수를 count
24
Simulation Results
Integral Deployment Model을 가정하고 시뮬레이션을 통해 VA image의 deployment 과정을 실험 (cont’d)
- EDD와 비교한 결과 100GB 메모리에서는 deployment 성공률이 3%, 40GB 메모리에서는 10% 상승함
- Stage environment의 메모리가 커지면 deployment 성공률이 상승: 당연한 결과
25
Conclusion and Discussion
Efficient Stage Scheduling for Virtual Appliance Service in Cloud System
- 본 논문에서는 VA service의 stage scheduling 문제를 전산학 및 산업공학에서 널리 쓰이는 job order scheduling
문제로 정의하여 total weight (cost)를 높일 수 있는 스케줄링 알고리즘을 제안하고 있다.
- 저자들은 먼저 less realistic 한 continuous job loading model에서 optimal order scheduling을 찾고 이를 이용해,
realistic 한 integral job loading 문제의 최적 스케줄을 찾을 수 있는 방법을 제안하고 있다.
Discussion
- 저자들은 처음에
를 가정하였는데 (without loss of generality), cloud 네트워크의 제공 대역폭이나
시스템의 HW 속도가 다양한 것을 고려하면 해당 가정을 없애는 것이 더 정교했을 것 같음
- 저자들의 가정에서 stage에 load된 VA image는 due date이 되는 순간에 바로 local cloud로 복사되며, 즉시
unload 된다고 했는데 stage loading 시간이 un-ignorable한 것을 고려한다면 un-loading 시간 역시도 unignorable 하다고 보는 것이 더 좋을 것 같음
- 제시하는 증명 과정이 매우 친절하지 못하다고 봄. 특히 각 증명의 의의를 조감하는 technical insight를 충분히
명시하지 않음으로써 독자가 why라는 의문을 끊임없이 가지게 된다는 점을 비판하고 싶음
26

similar documents