Data distribution management (DDM) is one of the most important filtering mechanisms in large scale distributed simulations. DDM has been successful in reducing the network traffic in some respect, but its capability is limited by the computational overhead for matching update regions and subscription regions that represent the interests of data producers and data consumers, respectively. For example, a typical DDM scenario is a battlefield simulation, where sensors are deployed to detect enemy movement. The enemy units are moving to a certain destination point and a sensor detects any enemy units. The update regions represent the location of enemy units with small rectangles, and the subscription regions represent the detecting ranges of the sensors. In this example, only if the update regions of the enemy units and subscription regions of the sensor overlap, the location of the enemy units will be routed by the DDM filtering mechanism. However, that mechanism produces high computational overhead because a matching process is performed to calculate the intersection between all pairs of update regions and subscription regions. As the previous matching algorithms do not consider the characteristics of the region distribution, it is difficult to select a matching algorithm that is appropriate for some region-distribution situations. In the case of large scale distributed simulations, such as a battlefield simulation, it will probably be a situation with large overlapping regions. The computational overhead of the matching process in large scale simulations is significant, because of superfluous intersections between regions.
First, in this dissertation, we propose a binary partition-based matching algorithm based on the divide-and-conquer approach to reduce the computational overhead in the matching process. The design goal of our algorithm is to perform binary partitioning that divides the regions into two partitions, the left-hand partition and right-hand partition, and to find out the overlap information that entirely cover those regions recursively, and then carry out the matching process. Specifically, the matching process is executed by comparing the intersections between regions in the different partitions. If the more regions in the different partitions, the less calculation of the intersection between these regions, which leads to the reduction of the matching operation that is used in the matching process. Because these regions exist in different partitions that are located in the ordered relation of partitions. The previous matching algorithms we have examined so far do not focus on the relative location of partitions to improve the overall performance of the matching process. The DDM Mode in the extended FEDEP allows us to design and develop the implemented matching algorithm in the DDM module and integrate on DDM Module in RTI software through interfaces of the module. In addition, a user enhances improvement of the reusability of the DDM module in RTI software through interfaces of the module.
Second, to meet the broad range of applications with diverse computation and communication requirements, this dissertation extends the federation development and execution process (FEDEP) with a DDM Support Infrastructure (DSI) designed to fit in modular architecture for a large scale distributed simulation with DDM mode and RTI mode. The extended process with DSI supports a configuration to promote extension and adaptation of a matching algorithm in modular DDM architecture of a LRC in DDM mode. The RTI mode facilitates the rapid integration of the matching algorithm on the RTI software which DDM module is a matching process of computing intersections of regions.
To evaluate the proposed algorithm, a set of experiments has been conducted with different numbers of regions and overlap ratios for various situations to reflect the region distribution. Our experimental results show that the proposed algorithm significantly performs better than the previous DDM matching algorithms in the execution time for the matching process. The proposed algorithm outperforms the previous matching algorithms in terms of execution time, when many regions are greatly overlapped. Moreover, as a real HLA-based distributed application that is more realistic, we have implemented a prototype in RTI mode and DDM mode and conducted experiments with both on real networks and simulated HLA/RTI networks. In more complex scenarios where the number of regions grows and the overlap ratio highly changes, the proposed algorithm is much better than the others and improves the scalability of DDM implementation for large scale distributed simulations.
분산 시뮬레이션은 지리적으로 서로 다른 곳에 위치한 독립적인 시뮬레이터들을 네트워크 상에서 서로 연결하여 메시지 전달과 시뮬레이션 시각 동기화를 통해 통합 시뮬레이션 시스템을 구축하는 기술이다. 대규모 분산 시뮬레이션의 경우에는 데이터를 주고 발을 때 좀 더 효율적으로 데이터를 분배함으로서 전체 시뮬레이션 성능을 높일 수 있다.
High Levle Architecure (HLA)는 IEEE 표준 1516으로, 서로 다른 프로그래밍 언어 및 플래폼, 시뮬레이션 알고리즘을 바탕으로 만들어진 이기종 시뮬레이터 간의 연동을 위한 명세이고 이 HLA 표준 규격대로 만든 소프트웨어가 Run Time Infrastructure (RTI)이다. HLA RTI는 여러 시뮬레이터 간에 통신을 할 때 네트워크 양을 줄이기 위해서 보내는 쪽에서 데이터의 필터링하는 데이터 분배 관리를 명세하고 이를 RTI 내부 데이터 분산 알고리즘을 통하여 처리한다. 이러한 데이터 분산 알고리즘은 시뮬레이터 간에 주고 받는 데이터 양이 많은 대규모 분산 시뮬레이션에서는 반드시 필요한 요구사항으로 이러한 알고리즘의 개발을 위해서 다양한 기술을 필요로 하며 일반적으로 많은 어려움이 따른다.
본 논문은 분산 시뮬레이션을 위한 데이터 분산 관리를 효율적으로 하기 위하여 이진 분할 정합 알고리즘을 제안하고 이를 내부 컴포넌트로 가진 데이터 분산 관리 시스템 실제 RTI에 적용할 수 있도록 확장한다. 이를 위해 데이터 분산 관리 시스템을 정의하고 이 내부의 데이터 구조와 데이터 분산 알고리즘인 정합 알고리즘을 제안한다. 여기에 쓰이는 데이터 구조는 이진 분할 영역 나무 구조이고 정합 알고리즘으로 정렬화된 위치 관계를 통하여 정합 함수를 수행할 때 계산 비용을 줄 일 수 있다.
또한 데이터 분산 관리 시스템으로 데이터 구조와 정합 알고리즘을 사용자가 직접 플러그인 할 수 있도록 확장하였다. 이 시스템은 최소한의 변경으로 하위 호환성을 외부 인터페이스 가진 시스템으로 런 타임에 알고리즘을 수정할 수 있다. 이를 통하여 나중에라도 성능개선을 위한 알고리즘이 적용할 수 있다. 또한, 독립적으로 구성하고 실행될 뿐 아니라, 실제 미들웨어인 RTI에도 잘 통합되어 이러한 것을 네트워크에 연결하거나 하지 않고 성능을 측정할 수 있다.
제안된 이진 분할 기반 정합 알고리즘의 효율성을 측정하기 위해 타 알고리즘들과 비교하여 보았다. 제안된 알고리즘이 기존에 제안된 알고리즘에 비해 데이터 구조의 구성비용과 정합비용을 획기적으로 줄일 수 있었다. 또한 이를 실제 RTI에 적용하여 분산 환경에서 실제 워 게임에서 사용되는 영역 데이터를 적용해본 결과 다른 알고리즘에 비해 평균적으로 우수한 성능을 나타내었다. 제안된 데이터 분산 관리 시스템은 CORBA 및 DDS, TENA와 같은 타 분산 시뮬레이션 엔진에 탑재될 수 있고 혹은 재사용 가능한 워크플로의 프레임워크에 서브컴포넌트로 들어감으로 전체 시스템 성능을 향상시킬 수 있다.
