Executing scientific workload is computation-intensive, thus time-consuming, however job completion time is a complex non-linear function of allocated resources and resource capability varies over time unpredictably. Moreover, resources are globally distributed but there is no universal computing platform and most of resources are temporally available and managed by different domain rules. Therefore, uncertainty on the job execution quality particularly arise from resource faults. In this dissertation, we thus concentrate on the two types of resource faults in distributed computing environments such as \emph{failure} and \emph{fragmentation}, which make the balanced and optimal scheduling decision further complicated and deteriorate the reliability of a generated solution. These problems have been known as NP-hard. However the existing heuristics which have been proposed to provide fault tolerance are even static to fluctuated availability, are biased to a specific objective or are strongly dependent on the problem one attempts to deal with. To develop a new heuristic mechanism specialized for the fault tolerant job scheduling over unreliable resources, we build a novel meta-scheduling framework (MSF) based on self-organized genetic algorithm (SOGA) which has a promising ability to search near-optimal solutions based on the concept of Pareto optimality within the reasonable time and space complexity even though failures are highly unpredictable and frequently occur. The ultimate objective of the dissertation is to investigate its effectiveness and superiority on the aforementioned platform-level vulnerabilities such as failure and fragmentation. The primary contributions of the dissertation are as follows.
This dissertation firstly proposes a self-organized genetic algorithm as the kernel process of the meta-scheduling framework. The proposed SOGA consists of two processes such as master and agents, where the master process sets the number of subpopulations and assigns different values of weight factors. Thus, this control scheme decomposes the whole population into small ones each is managed by an agent process, so that search efficiency can be highly improved by letting each agent focuses on a particular region of the overall search space. Then, the SOGA adjusts tradeoff between diversity quality and convergence speed in performing the local and global search during optimization according to quality values of individual solutions in order to prevent search points from being stuck in some local region containing locally optimal solutions. The third control scheme applied in the SOGA is a global archive, which maintains non-dominated solutions only based on the concept of Pareto frontier. This implies that the best solutions generated by agents can be interactively shared among subpopulations, so that diverse solutions are introduced to each subpopulation at every generation. The SOGA demonstrates its effectiveness and strengths in terms of time and space complexity, algorithmic scalability, fault tolerance compared with Min-Min algorithm and hill climbing search.
Secondly, we propose a multihybrid job scheduling (MJS) scheme in order to deliver robust resource allocation for computational batch jobs under heterogeneous rescheduling policies. To effectively solve a multihybrid policy decision problem (MPDP) on the primary-backup fault tolerance model, we first construct the MJS scheme, according to the stochastic search operations of SOGA. On account of inherent specialty of MPDP, we then propose two processes for solution representation, which codifies a schedule to the MPDP and solution realization, which computes sequences and time slots of each job, in order to make SOGA compatible with the MPDP. Simulation results show the superiority of the SOGA based MJS scheme compared with other static rescheduling policies in terms of three main metrics such as makespan, average utilization, and job failure rate over DCS with identical policies. Also, the proposed mechanism makes full use of each resource’s capacity and highly improves the search efficiency compared to a deterministic heuristic (e.g., Min-Min algorithm) in every category of policy constraints. Namely, the proposed MJS mechanism based on the SOGA is especially useful when allocating the sequential batch jobs to resources adopting different types of rescheduling policies in distributed computing systems with various obstacles.
To analyze the effects of resource fragmentation, we thirdly propose a new state-tracking migration scheme that is integrated with aggressive reservation strategies such as immediate restart, greedy backfilling and selective preemption. We start with an analysis of three commonly occurred problems: job restart delay, inter-job delay, and delayed job execution. Then we discuss how to estimate the expected runtime with our resource failure model and proposed three aggressive reservation strategies mentioned above. To combine each strategy into the batch mode scheduling, we also adopt the SOGA based allocation framework. One key objective of this research is to investigate how effectively STMS with each strategy reactivates a failed job to reduce the three inevitable delays. We observe how the proposed migration schemes take advantage of idle time slots for jobs to optimize the performance benefit without compromising the inter-job fairness. The simulation results suggest that state-tracking migration with selective preemption entirely outperforms the others.
As the feasibility study, we further consider cooperative media computing services where resources are voluntary and volatile in order to assess the performance of the SOGA based reactive job scheduling for a different type of resource faults (i.e., networking fragmentation). In appendices, we then extend the third study to be robust against the random fragments by proposing a SOGA based cooperative media scheduling mechanism with different resource reservation strategies, which update a group of corresponding super-peers by adding new neighbors for reactively compensating the networking availability losses. Simulation results show that the proposed scheme can highly improve the overall quality of media distribution without violations of layer, transmission and bandwidth constraints.
대단위 자원의 접근 및 사용을 요구하는 과학용 워크로드 (Workload)는 계산 복잡도가 높아 매우 긴 실행 시간을 갖는 특성이 있다. 그러나, 워크로드의 논리적 실행 단위인 Job의 수행 시간은 할당된 자원 성능과 비선형적 (Non-Linear) 상관관계를 갖으며, 자원 성능 역시 시간에 따라 예측하기 어려운 특성 (Time-Variant)이 있다. 이와 같은 불확실성을 기본적으로 내포한 분산 컴퓨팅 환경에서 과학 응용 프로그램 및 서비스의 빠르고 신뢰적인 실행을 보장하기 위해서는, 자원 브로커링 시스템을 도입하여 지리적으로 분산된 대규모 자원의 통합된 성능을 관측하고 이를 기반으로 가용한 자원을 동적으로 선정하여 Job에 할당할 필요성이 있다. 이와 관련된 일련의 주요 과정은 자원 브로커링 시스템 내부적으로 Job 스케줄러에 의해 수행되고 있어, 거대 워크로드의 처리 및 해석에 있어 Job 스케줄러 적응적 의사결정 기능의 중요성이 매우 높다고 평가할 수 있다. 최근 거대 복잡도를 요구하거나 데이터 집약적 특성을 갖는 워크로드의 처리는 과학자, 공학자 및 시스템 엔지니어와 같은 다양한 개별 연구 주체의 공여 시스템을 기반으로 구성된 다중 협업 환경에서 진행되고 있다. 이는 공여 자원의 비용 대비 활용도가 매우 높다는 사실에 기인한다. 그러나 공여 자원들은 단일 소유권에 의해 중앙에서 통제되기 어렵고, 별도의 관리 도메인 상에 존재하므로 내부 정책에 의해 그 구체적인 운용 정책이 결정되고 이를 기반으로 관리되는 특성이 있다. 또한 자원에 따라 상이한 분산 컴퓨팅 플랫폼 또는 미들웨어를 탑재하고 있어, 자원 결함으로 인한 워크로드 실행의 실패 또는 중단 등의 문제에 대처하기 어렵다는 매우 심각한 한계점을 안고 있다. 따라서, 기존의 스케줄링 시스템 상에서는 상이한 관리 정책에 의해 운용되는 도메인 간의 (Domain Cross) 자원 공유를 통한 대단위 성능을 이끌어 내기 어렵다. 특히 상기 언급한 문제점들은 스케줄러의 워크로드 실행 시간 예측의 불확실성을 가중시켜, 스케줄링 솔루션의 적합도 (Fitness)를 크게 훼손할 가능성이 높다. 그러므로, 본 논문에서는 대단위 협업을 지원하는 공여 자원 집단의 상이한 시스템 구성에도 불구하고, 결함으로 인한 스케줄링 불확실성의 증가를 최소화하여 본 시스템이 갖는 비용 대비 성능을 극대화할 수 있는 결함 감내형 스케줄링 시스템을 제안하고자 한다.
기존의 휴리스틱 스케줄링 기법들은 제한적 문제에만 적합한 형태로 고안되었거나, 특정한 목적 함수에 특화되어 제안된 측면이 강해 해결하고자 하는 공학적 문제가 가지고 있는 고유의 특성들과 환경적 구성요건에 매우 종속된 것으로 고려할 수 있다. 또한 종래의 기법들이 단일 변수로 구성된 목적함수에서 우수한 최적해 탐색 성능을 보일 수 있으나, 다목적 함수를 대상으로 최적해를 보장하지 못하는 취약점을 가지고 있다는 사실은 이미 널리 검증된 바 있다. 특히, 이기종의 분산 자원에서 결함 발생을 고려하여, 최적의 스케줄링 해를 구하는 문제는 NP-Hard한 것으로 수학적으로 규명된 바 있으며, 또한 이를 해결하기 위한 닫혀진 형태의 수식 (Closed-form Formula) 역시 존재하지 않는 것으로 증명되었다. 따라서, 본 논문에서는 기존 휴리스틱 기법이 갖는 `탐색의 단순성 (Greedy), 편향적 해 선택성 (Biased), 해 탐색의 국지성 (Premature Convergence)`이라는 세 가지 제약 사항을 개선하기 위해 많은 응용 사례와 실험 결과를 기반으로 검증된 바 있는 유전 알고리즘 (Genetic Algorithm)의 이론적 근거를 활용하여, 다목적 최적 조합 문제(Multi-Objective Combinatorial Optimization Problem)로 정형화될 수 있는 Job 스케줄링 문제에서 최적 근접 해(Near-Optimal Solution)의 탐색을 시간 및 공간 복잡도 측면에서 신뢰적으로 보장해줄 수 있는 자가 동적 유전 알고리즘 (SOGA: Self-Organized Genetic Algorithm)을 제안한다. SOGA은 본 연구에서 제안하는 메타 스케줄링 프레임워크 (Meta-Scheduling Framework)의 근간을 이루는 가장 핵심적인 기법으로서 `1) Job과 자원간의 할당 관계를 연속적 배열로 표현하여, 다양한 스케줄링 솔루션 형태를 정의할 수 있는 인코딩 스키마 (Encoding Schema), 2) 마스터 프로세스를 통해 초기 개체군 (Population)을 생성하고, 이를 부분 개체군 (Subpopulation)으로 분할하여 개별 에이전트 프로세스에게 할당하며, 이때 개별 에이전트 프로세스가 탐색할 영역을 국지화 시킬 수 있도록 목적 함수의 가중치 값을 다르게 부여하는 부분 개체군 관리 기법, 3) 각 에이전트 프로세스에서 SOGA 기반의 탐색 오퍼레이션 수행 시, 탐색 영역을 다변화시킬 것인지 또는 국지화시킬 것인지 여부를 동적으로 결정할 수 적응적 탐색 파라미터 조정 기법, 4) 개별 에이전트 프로세서가 관리하는 부분 개체군으로부터 각 세대 (Generation) 마다 생성된 가장 좋은 해를 보존하고, 각 에이전트 간의 다양한 해의 공유가 가능하도록 돕는 전역 아카이브 (Global Archive) 기법` 와 같은 4 가지 세부 제어 기법을 기반으로 동작한다. 특히, SOGA는 최적해에 ε만큼의 경쟁력 (ε-competitive)을 갖는 근사해를 탐색하여 스케줄러에 제공함으로써, 스케줄링 솔루션의 품질 (Quality) 하락은 최소화하면서, 동시에 최적해 탐색에 따른 해 탐색 시간을 크게 단축시킬 수 있는 강점을 제공한다. 본 기법은 MMA (Min-Min Algorithm) 및 HCS (Hill Climbing Search)와 같이 비교적 우수한 성능을 보장하는 것으로 판명된 종래의 휴리스틱 알고리즘에 비해 실험적으로 가장 낮은 시간$\cdot$공간 복잡도를 보장하였으며, 탐색하고자 하는 문제의 크기가 매우 큰 경우 (N × M = 50,000 × 400)에도 가장 우수한 솔루션 적합도를 제공하는 것으로 평가되었다.
다음으로 본 논문에서는 자원마다 상이한 재할당 정책(Heterogeneous Rescheduling Policy)들을 지원하여 결함 대응 스케줄링 기법을 제공하기 어려운 분산 컴퓨팅 환경에도 불구하고, 결함 내성을 향상시키기 위해 개별 Job 수행 중 문제 발생 시 다양한 도메인으로부터 사전 계획된 (Proactive) 백업 자원을 적응적으로 제공함으로써 Job 수행의 중단을 최소화시키는 MJS (Multihybrid Job Scheduling) 기법을 고안하였다. 본 고안된 MJS 기법을 이용하기 위해서는 다양한 결함 대응 정책들을 해 탐색 시 SOGA에 반영할 필요가 있어, 이를 기존의 스케줄링 문제보다 복잡도가 매우 높은 MPDP (Multihybrid Policy Decision Problem) 문제로 정의하였고, 이의 해결을 위해 먼저 기존 인코딩 스키마를 하나의 Job에 복수개의 자원을 할당할 수 있는 구조로 확장하였다. 또한, 특정 재할당 정책에 의해 상이하게 제어되는 Job의 확률적 실행 시간 (PET: Probabilistic Execution Time)을 산정하는 알고리즘과 재할당 정책에 따른 Job간의 선행 관계 (Precedence Constraint)를 결정짓는 알고리즘을 해 적합도 평가 시 반영하도록 SOGA를 개선하였다. 대단위 분산 컴퓨팅 시스템으로부터 실측된 결함 Trace 데이터를 SOGA 기반 시뮬레이션에 반영하고, 자원마다 지원하는 재할당 정책을 동적으로 제한하는 실험적 환경 하에서 제안된 MJS 기법 평 가 시 MMA와 같은 기존 휴리스틱에 비해 SOGA가 보다 적응적으로 각 재할당 기법의 장점을 활용하여 Job 완료시간 (Makespan), 이용률 (Utilization) 및 실패 비율 (Failure Rate)을 보다 빠른 시간내에 공히 최적화시킬 수 있는 것으로 판명되었다.
자원 결함은 상기 MJS 기법에서와 같이 슈퍼 스케줄러의 능동적 결함 감내 기법에 의해서 상당 부분 제어될 수 있으나, 잦은 결함 발생으로 인한 재할당 기법들의 빈번한 사용은 기존 스케줄링 구성의 단편화 (Fragmentation)를 초래할 수 있다. 따라서, 자원 성능이 크게 낭비될 수 있을 뿐만 아니라, 결과적으로 자원의 과할당 (Overprovisioning)을 유발할 수 있다. 본 문제의 해결을 위해서는 로컬 스케줄러에서 단일 자원에 할당된 스케줄링 솔루션을 동적으로 재구성할 필요가 있다. 본 논문에서는 세번째 제안으로 자원의 성능 활용도를 극대화하기 위해 적극적인 자원 예약 재구성 기법으로 `Immediate Restart Strategy (IRS), Greedy Backfilling Strategy (GBS) 및 Selective Preemption Strategy (SPS)`을 제안하였고, 이들 기법간의 성능 우위를 평가하기 위해 상기 MPDP 문제에서 가정한 재할당 기법중 상태 추적형 마이그레이션 (State-tracking migration)을 기반으로 결함 감내형 스케줄링 솔루션이 결정되는 환경을 가정하였다. 특히 SPS 기반의 솔루션 재구성 기법이 GBS 및 IRS에 비해 전반적으로 우수한 성능을 보장하는 것으로 평가되었는데, 이는 마이그레이션 재할당으로 인해 유발되는 Job의 지연 실행을 최소화시키는 것이 Job간 낭비되는 공간을 줄이는 것에 비해 보다 우수한 단편화 대응 전략임을 의미하는 것으로 판단할 수 있다. 특히 본 논문에서는 부가적인 연구 성과로서, SOGA의 로컬 스케줄러로서의 현실적 활용 가능성의 가치를 보다 면밀히 평가하기 위해 기존 평가 방식과는 달리 데이터 집약적이고 실시간 데이터 전송을 요구하며 자원들이 보다 동적으로 자원 그룹에 임의 참여하거나 탈퇴하는 보다 복잡한 자원 공유 환경을 가정하였고, SOGA 기반의 협력적 미디어 스케줄링 기법이 어느 정도 기민하게 이와 같은 환경적 제약사항에도 불구하고 특정 결함 감내의 정도를 보장할 수 있으며, 동시에 미디어 컴퓨팅 서비스를 안정적으로 유지시킬 수 있는지를 정량적으로 평가하고자 하였다. 이를 위해 먼저 개별 노드 (Node)에서 SOGA 기반의 로컬 스케줄링을 실시하여 생성된 초기 솔루션에 따라 복수개의 자원으로부터 병행적으로 데이터를 수신하는 LSON (Layered Streaming in Super-Peer Overlay Networks) 모델을 정립하고, 데이터의 손실 또는 지연 시 보다 우수한 데이터 전달 자원 (Super-Peer)을 피어 유용성 프로모션 (Peer-Utility-Based Promotion) 기법을 통해 선정하고, 이를 전달 자원 그룹에 추가 반영하여 스케줄링 솔루션을 재구성하는 기법을 제안하였다. 특히 제안된 기법은 전역 최적화 (Global Optimization) 방법론을 사용하여 획득한 스케줄링 솔루션에 비해 평균적으로 2.9% 이내의 적합도 손실을 보장하며, 데이터 스트리밍 서버의 대역폭 의존도를 최소화할 수 있는 것으로 판명되었다. 또한, 스케줄링 재구성에 따른 시간 오버헤드가 데이터 요청 주기에 비해 현저히 작은 것으로 실험 결과 밝혀졌다.
상기 언급한 바와 같이 SOGA 기반의 메타 스케줄링 프레임워크 (Meta-Scheduling Framework)은 사전적 결함 감내형 기법을 통해 다양한 재할당 정책 및 백업 자원의 성능을 동시에 고려하여 근사 최적 스케줄링 솔루션을 생성하는데 탁월한 우수성을 보장하며, 빈번한 재할당 정책의 사용으로 인한 자원 단편화의 문제점을 최소화하기 위해 로컬 스케줄러와의 협업이 가능한 구조적 장점을 지원한다. 더불어, 서비스 실시간성을 요구하는 분산 컴퓨팅 환경에서 SOGA 기반 제안 기법이 로컬 스케줄러로 확장되어 구성되더라도 최적 수준에 근사한 서비스 품질을 보장할 수 있는 것으로 판명되었다. 따라서, 제안한 SOGA 기반의 스케줄링 메커니즘이 기존의 타 휴리스틱 기법들에 비해 보다 다양한 분산 컴퓨팅 문제를 해결하는데 기여할 수 있으며, 또한 현실적 적용 가능성 역시 매우 높은 것으로 사료된다.
