최근에 정보네트워크 사용자의 급증에 따라 DDS(Distributed Database System)는 VAN(Value Added Network)상에서 구현되었다. DDS는 지역적으로 분산된 작업환경에서 중앙집중식 데이터베이스 구축보다 여러 측면에서 장점이 있으나 불합리한 설계는 컴퓨터 및 네트워크 자원의 비효율적 사용에 의한 비용의 증가와 데이터 유지를 위한 복잡도의 증가를 야기한다. DDS 설계시 각 사이트에서 적절한 컴퓨터를 선택하는 문제와 단편화된 데이터를 적절한 사이트에 할당하는 문제가 중요하다. VAN 상에서 컴퓨터 선택과 데이터 파일의 할당은 응답대기시간(waited response time)과 투자비용(investment cost)의 상관관계를 반드시 고려하여 결정되어야 하므로, 본 논문에서는 각 컴퓨터와 파일의 할당의 영향에 따라 두 목적함수의 상관관계를 고려한다. 특히, 응답대기 시간에 대한 보다 실제적인 평가를 위해 M/M/1 큐잉 시스템을 기초로 하여 설계한다. 제안된 설계모델은 경험적 탐색법 중의 하나인 유전자 알고리즘(Genetic Algorithm)의 적용을 통해 효율적인 해의 탐색을 시도하고 제안된 수학적 모델과 알고리즘의 성능 검토를 위해 모의실험 및 결과분석을 한다.
최근에 정보네트워크 사용자의 급증에 따라 DDS(Distributed Database System)는 VAN(Value Added Network)상에서 구현되었다. DDS는 지역적으로 분산된 작업환경에서 중앙집중식 데이터베이스 구축보다 여러 측면에서 장점이 있으나 불합리한 설계는 컴퓨터 및 네트워크 자원의 비효율적 사용에 의한 비용의 증가와 데이터 유지를 위한 복잡도의 증가를 야기한다. DDS 설계시 각 사이트에서 적절한 컴퓨터를 선택하는 문제와 단편화된 데이터를 적절한 사이트에 할당하는 문제가 중요하다. VAN 상에서 컴퓨터 선택과 데이터 파일의 할당은 응답대기시간(waited response time)과 투자비용(investment cost)의 상관관계를 반드시 고려하여 결정되어야 하므로, 본 논문에서는 각 컴퓨터와 파일의 할당의 영향에 따라 두 목적함수의 상관관계를 고려한다. 특히, 응답대기 시간에 대한 보다 실제적인 평가를 위해 M/M/1 큐잉 시스템을 기초로 하여 설계한다. 제안된 설계모델은 경험적 탐색법 중의 하나인 유전자 알고리즘(Genetic Algorithm)의 적용을 통해 효율적인 해의 탐색을 시도하고 제안된 수학적 모델과 알고리즘의 성능 검토를 위해 모의실험 및 결과분석을 한다.
Recently, DDSs(Distributed Database Systems) have been implemented on V AN(V alue Added Network) as we know the amazing expansion of information network. DDS can yield significant cost and response time advantages over centralized systems for geographically distributed organizations. However, inappr...
Recently, DDSs(Distributed Database Systems) have been implemented on V AN(V alue Added Network) as we know the amazing expansion of information network. DDS can yield significant cost and response time advantages over centralized systems for geographically distributed organizations. However, inappropriate design can result in high cost and poor response time to maintain the database at each site. In a DDS design, the main problem is how to select proper computer and how to allocate data fragment into a proper site. In this paper, we address DDS design problem of selecting the proper class of computers and the allocating data files on VAN. Also, the formulated model includes two objectives, the waited response time and the investment cost to include their relationship. Specially, the formulation of waited response time is based on M/M/1 queueing system to evaluate more precisely. GA(Genetic Algorithm), a kind of heuristic search method, is developed to search an optimal solution in the proposed design model and we show the simulation result to examine the algorithm performance.
Recently, DDSs(Distributed Database Systems) have been implemented on V AN(V alue Added Network) as we know the amazing expansion of information network. DDS can yield significant cost and response time advantages over centralized systems for geographically distributed organizations. However, inappropriate design can result in high cost and poor response time to maintain the database at each site. In a DDS design, the main problem is how to select proper computer and how to allocate data fragment into a proper site. In this paper, we address DDS design problem of selecting the proper class of computers and the allocating data files on VAN. Also, the formulated model includes two objectives, the waited response time and the investment cost to include their relationship. Specially, the formulation of waited response time is based on M/M/1 queueing system to evaluate more precisely. GA(Genetic Algorithm), a kind of heuristic search method, is developed to search an optimal solution in the proposed design model and we show the simulation result to examine the algorithm performance.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
돌연변이 연산은 전체 염색체에 대해 임의로 변환되는 특성에 의해 해공간에서 전역적인 탐색을 가능하게 함으로써 대개 교배연산의 협소한 탐색을 보안하기 위해 설계된다. 본 논문에서 제안한 돌연변이 연산은 각 선택된 사이트 내에서 컴퓨터 계층도 재생성 되는 것을 제외하고는 앞 절에서 기술한 교배와 거의 유사하고 (그림 4)에서처럼 다음의 과정에 따라 수행된다.
DDS 설계 문제는 매우 어려운 작업(hard combinatorial problem)으로서 네트워크 문제와 파일의 할당(컴퓨터선택) 문제와의 밀접한 상관관계를 가짐으로 반드시 동시에 고려되어야 한다. 따라서 본 연구에서는 VAN 상에서의 단편화된 데이터의 할당문제와 네트워크 문제를 동시에 고려하여 IC 및 WRT를 최소화하면서 각 사이트에 적합한 컴퓨터를 선택하고 파일 할당을 하는 효율적인 분산데이터베이스를 설계한다. 특히, WRT를보다 정확하게 평가하기 위해 큐잉 시스템(queueing system)을 도입하여 통신지연(communication delay), 디스크 입출력 지연(disk I/O delay), CPU 지연(CPU delay)으로 세분화하여 고려하였다.
본 장에서는 제안된 설계모델에서 각 사이트에서 최적의 컴퓨터 계층과 단편화된 데이터의 할당을 의미하는 최적해를 탐색하기 위해 GA 설계에 관한 논의를 한다. 2.
본- 연구에서 WRT와 IC의 상관관계를 고려하면서 단편화된 데이터 파일을 적합한 사이트로 할당하고 각 사이트에 대한 적합한 컴퓨터 계층을 선택하는 문제를 다루었다.
즉, 각 계층화된 작업이 수행되는 컴퓨터 플랫폼과의 상관관계를 고려하고 밀접한 관련성을 가지는 WRT와 IC를 DDS 설계를 위한 평가함수로써 동시에 고려하였다. 무엇보다도 설계모델에서는 이질 기종의 컴퓨터 상에서 발생하는 트랜잭션의 집합인 작업을 5개의 계층으로 세분화하여 각 작업이 수행될 때의 IC와 MFT의 상관관계의 고려에 역점을 두었다.
가설 설정
1) 한 사이트에 한 개의 컴퓨터만 설치돨 수 있다. S < 1 for s w S
2) 각 사이트의 주기억장치양은 도착하는 작업을 처리하는데 충분해야 한다.
5) 각 사이트에 할당된 데이터파일이 존재하기 위해서는 기억장치를 보유한 컴퓨터가 설치되어져 있어야만 한다.
제안 방법
2.2 절에서 기술한 제약조건을 검사하고 2.1 절에서 기술한 두 목적함수로부터 유도되는 평가함수를 통해 해의 질(quality)을 평가한다,
VAN상에 구현하는 문제를 다룬다. GA의 진화환경 인자로서 최대 세대수 max_gene2000, 교접확률 奴 = 0.3, 돌연변이 확률 Pm = Q.2, 집단크기 pop_ g=20으로 두고 수행하였다.
그러므로 본 연구에서는 염색체 표현에 있어서 메모리 공간의 효율적 사용과 제약조건을 최소로 위반하도록 설계에 중점을 두었고 제안한 염색체 구조를에 나타내었다.
매우 난해한 문제로 유도되는 제안된 다목적 함수 모델(multiobjective function mo(坷)에서 효율적인 해를 탐색하기 위해 설계된 GA에서는 염색체 표현에서 행렬을 기반으로 한 유전자 표현에 비해 메모리 자원의 절약과 기본적인 제약조건식을 위반하지 않는 장점을 가지도독 설계에 중점을 두었다. 모의실험을 통한 성능 검토에서 GA 수행 후 파레토 해를 결정자에게 제공함으로써 각 목적의 중요도에 따라 DDS 구조를 선택할 수 있는 방안을 제시하였다.
가지도독 설계에 중점을 두었다. 모의실험을 통한 성능 검토에서 GA 수행 후 파레토 해를 결정자에게 제공함으로써 각 목적의 중요도에 따라 DDS 구조를 선택할 수 있는 방안을 제시하였다.
즉, 각 계층화된 작업이 수행되는 컴퓨터 플랫폼과의 상관관계를 고려하고 밀접한 관련성을 가지는 WRT와 IC를 DDS 설계를 위한 평가함수로써 동시에 고려하였다. 무엇보다도 설계모델에서는 이질 기종의 컴퓨터 상에서 발생하는 트랜잭션의 집합인 작업을 5개의 계층으로 세분화하여 각 작업이 수행될 때의 IC와 MFT의 상관관계의 고려에 역점을 두었다.
본 논문에서 고려하는 DDS 설계모델에서의 WRT 는 각 사이트에서의 통신 네트워크의 사용에 의한 지연시간(communication delay), 디스크 I/O 사용에 의한 지연시간(disk I/O delay), 그리고 CPU 사용에 의한 지연시간(CPU delay)으로 유도된다. 이들 각각의 요소에 따른 지연시간에 대한 전체적인 구조는 ■림1과 같다.
설계된다. 본 논문에서 제안한 돌연변이 연산은 각 선택된 사이트 내에서 컴퓨터 계층도 재생성 되는 것을 제외하고는 앞 절에서 기술한 교배와 거의 유사하고 (그림 4)에서처럼 다음의 과정에 따라 수행된다.
본 논문에서 제안한 설계모델과 GA의 성능을 평가하기 위해 5개의 사이트와, 5개의 컴퓨터와 작업 계층 그리고 8개의 데이터 파일들을 포함하는 분산 데이터베이스를 VAN상에 구현하는 문제를 다룬다. GA의 진화환경 인자로서 최대 세대수 max_gene2000, 교접확률 奴 = 0.
본 논문에서는 제안된 모델에서 효율적인 해를 탐색하기 위해 경험적 탐색법(heuristic search method) 중의 하나로써 통계적 탐색(statistic sear산!)[6]을 하는 유전자 알고리즘(Genetic Algorithm : GA)의 적용 방법을 제안한다. 제안된 수학적 모델을 풀기 위해 GA를 사용하는 주요한 이유는 다음 두 가지 장점으로 요약할 수 있다.
본 논문에서는 최적화 문제로서 상호 밀접한 연계를 가지는 응답대기 시간(Waited Response Time : WRT) 과 투자비용(Investment Cost : IC)을 고려하였고 컴퓨터의 이질 기종 상에서의 분류된 트랜잭션 처리에 대한 영향을 고려하였다. 응답대기시간은 사용자로부터 질의가 발생된 후 그 결과를 사용자에게 제공하기까지의 시간으로 정의되고, 투자비용은 각 사이트에서의 컴퓨터 시스템을 설치하는 비용으로 고려하였다.
제안돤 수학적 모델에서 WRT를 계산하기 위해 M/M71 큐잉이론을 기초로 하여 각각의 통신지연, disk I/O 지연, CPU 지연시간을 고려하였고 무엇보다도 컴퓨터의 이질 기종 상에서 수행되는 작업의 크기(granularity) 를 계층화함으로써 보다 살제적인 DDS의 설계모델을 제안하였다. 즉, 각 계층화된 작업이 수행되는 컴퓨터 플랫폼과의 상관관계를 고려하고 밀접한 관련성을 가지는 WRT와 IC를 DDS 설계를 위한 평가함수로써 동시에 고려하였다.
해공간에서 지역적인 탐색을 한다. 제안된 교배에서도 기본적인 제약조건을 위반하지 않는 염색체를 생성하도록 설계에 중점을 두었고 선택된 부모의 양질의 유전자를 각 자식(offspring)들에게 유전되도록 하였다. (그림 3)에서처럼 교배는 다음의 과정을 통해 이루어진다.
제안된 두 유전자 연산자 교배와 돌연변이는 제약 조건식을 위반하는 해의 변환은 비가능해를 생성함으로써 이를 검출하고 조정하기 위한 수행 복잡도를 가중시키기 때문에 기본 제약조건식 (4), (7)을 반드시 보장하도록 설계하였다.
제안된 모델에서는 두 개의 다목적 함수를 고려함으로써 하나의 해에 대해 두 목적 함수를 동시에 공정하게 평가해야 한다. 대개 임의의 해에 대해서 WRT가 우수한 경우에 대해서 IC측면에서는 비효율적인 상관관계를 가지기 때문에 두 목적함수의 공정한 평가를 위해 Gen[6]°l 제안한 가중치합법(weighted sum method)를 이용하고 두 목적의 상관관계에 따라 결정자(decision maker)가 해를 선택하기 용이하도록 파레토 해(Pareto solution) 표현한다.
따라서 본 연구에서는 VAN 상에서의 단편화된 데이터의 할당문제와 네트워크 문제를 동시에 고려하여 IC 및 WRT를 최소화하면서 각 사이트에 적합한 컴퓨터를 선택하고 파일 할당을 하는 효율적인 분산데이터베이스를 설계한다. 특히, WRT를보다 정확하게 평가하기 위해 큐잉 시스템(queueing system)을 도입하여 통신지연(communication delay), 디스크 입출력 지연(disk I/O delay), CPU 지연(CPU delay)으로 세분화하여 고려하였다.
본 문제에서 제안한 두 목적함수는 최소화 문제이기 때문에 F+ 영역에 파레토 해들이 존재함을 알 수 있다. 파레토 해집합 F와 두 좌표는 각 세대별로 갱신되고 세대의 진화에 따라 두 좌표에 의한 직선은 효율적인 해의 탐색을 하도록 한다. 가중치합법을 기초로 한 평가함수를 다음과 같이 제안한다.
이론/모형
본연구에서는 평가함수치가 우수한 해부터 정렬하고 효율적인 해부터 우선순위(priority)를 가지고 다음 세대에 포함되도록 차별화를 주는 방법인 엘리트 선택법 (elitist selection method)을 응용한다.
그림으로 나타내고 있다. 추출된 파레토 해 집합에서 두 목적 함수의 상관관계를 고려하여 가장 타협적인 해(the best compromised solution)# 구하기 위해 Yoon과 Hwang[13]이 제안한 TOPSIS 방법을 웅용하였다.
성능/효과
3) 각 사이트의 보조기억장치양은 그 사이트에 할당되어진 데이터 파일의 모든 사본을 저장 할 수 있도록 충분해야 한다.
4) 각 데이터 파일은 적어도 하나의 사이트에는 반드시 할당되어야 하고, 하나의 데이터 파일에 대해서는 여러 사이트로의 중복 할당이 허용된다.
우수하다. 그리고 동일 데이터의 각 사이트로의 중복할 당은 질의가 발생한 사이트에서의 로컬처리를 가능하게 함으로써 원격 사이트로의 데이터 참조를 위한 추가적인데 이 터 전송시간이 요구되지 않기 때문에 WRT에 대해 우수하지만 추가적인 갱신시간(data updating time) 이 가중된다는 점을 알 수 있다.
좌표■ ( 初前, 2] 皿)와 ( emax , 成 血)으로 형성된 직선은 제약조건을 만족하는 타원 내부에서 F+ 영역과 F- 영역으로 분할된다. 본 문제에서 제안한 두 목적함수는 최소화 문제이기 때문에 F+ 영역에 파레토 해들이 존재함을 알 수 있다. 파레토 해집합 F와 두 좌표는 각 세대별로 갱신되고 세대의 진화에 따라 두 좌표에 의한 직선은 효율적인 해의 탐색을 하도록 한다.
후속연구
즉, 제약조건식 (4)와 (7)이 염색체 구조 자체로써 제약조건을 위반하는 비가능해(in- feasible solution)를 생성하지 않는다. 단, 제약조건 (7)을 만족시키기 위해 같은 사이트 내에 동일한 데이터파일이 중복할당 되었는지 검사하는 절차가 추가로 요구된다.
그러므로 모델의 설계에 있어서 중요한 요인(factor)으로서 시스템 오류에 대한 신뢰성을 극대화시키는 고려가 필요하다. 둘째는 최근 급증하는 인트라넷의 구축에 따라 LAN환경에서 DDS 를 구축하는 문제를 둘 수 있고 평균 지연시간을 최소화하는 네트워크 라우팅(network routing) 문제와 데이터의 형태가 다양해짐에 따라 분산 환경에서의 이종 데이터 베이스간의 상관관계를 고려한 멀티미디어 DDS 구현에 대한 연구가 필요하다.
제안된 교배만으로는 협소한 해공간을 탐색함으로써 효율적인 해의 탐색시간이 오래 걸리고 극소해에 수렴할 가능성이 있으므로 해공간의 탐색 범위를 보안하기위한 돌연변이 연산이 필요하다.
참고문헌 (17)
S. T. March and S.K. Rho, 'Allocating Data and Operations to Nodes in Distributed Database Design,' IEEE Trans. on Knowledge and Data Engg., Vol.7, No.2, pp.305-317, Apr. 1995
M. Ozsu and P. Valduriez, 'Principles of Distributed Database Systems', Prentice-Hall Inc., Englewood Cliffs, N.J. 1991
S. Ram and R. E. Marsten, 'A Model for Database Allocation Incorporating a Concurrency Control Mechanism,' IEEE Trans. on Knowledge Data Eng., Vol.3, pp.389-395, Sep. 1991
H. K. Jain, 'A Comprehensive Model for the Design of Distributed Computer Systems,' IEEE Trans. on Software Eng., VoI.SE-13, pp.1092-1104, Oct. 1987
M. Gen and R. W. Cheng, 'Genetic Algorithms and Engineering Design,' John Wiley and Sons, New York, 1997
Z. Michalewicz, 'Genetic Algorithms+Data Structures Evolution Programs,' second edition, Springer-Verlag, New York, 1994
R. J. A. Buhr and C. M. 'Woodwide, Microscopic Economic Planning Models for Distributed Infor-mation Systems,' INFOR, Vol.15, No.2, 1977
I. Mitrani and Sevcik, 'Evaluating the Trade-off between Centralized and Distributed Computing,' Proc. 1st Int. Conf. Distributed Computing Systems, pp.520-528, Oct. 1979
W. W. Chu, 'Optimal File Allocation in Multiple Computer Systems,' IEEE Trans. Comput., Vol.C-18, pp.885-889, 1969
S. Mahmoud and J. S. Riordan, 'Optimal Allocation of Resources in Distributed Information Networks,' ACM Trans. on Database System, Vol.1, No.1, pp.66-78, 1976
J. P. Ignizio, D. F. Palmer, and C. Murphy, 'A Multicriteria Approach to Super System Architecture Definition,' IEEE Trans. on Comput., Vol.C-31, pp.410-418, May 1982
A. Dutta and H. Jain, 'A DSS for Distributed Computer System Design in the Presence of Multip-le Conflicting Objectives,' Decision Support System, Vol.1, No.3, pp.233-246, Sept. 1985
C. Hwang and K. Yoon, 'Multiple Attribute Decision Making Methods and Applications,' Springer-Verlag, Berlin, 1981
M. Gen, Y. Tsujimura and S.B. Ko, 'Allocation Strategy for Distributed Database System with Fuzzy Data Using Genetic Algorithm,' 5th European Congress on Intelligent Techniques and Soft Com-puting (EUFIT'97), Vol.1, pp.737-742, Sep. 1997
S. Ko, Y. Tujumura and M. Gen, 'Data Distribution Considered Communication Flow in Network Using Genetic Algorithm,' 2nd Inter. Conf. on Knowledge-Based Intelligent Electronic Systems, Vol.2, pp, 264-271, Apr. 1998
J. Jo, S. Ko, S. Yoon, Y. Tsujimura, and M. Gen, 'Processor Selectio and Data Allocation Problem in Distributed Database System Using GA,' Inter. Conf. on APIEMS, pp.357-360, Oct. 1999
D. C. Little, 'A Proof of the Queueing Formula L ${\lambda}$ W,' Operation Res.,' Vol.9, pp.383-387, 1961
※ AI-Helper는 부적절한 답변을 할 수 있습니다.