Performance analysis of an adaptive dynamic grid-based approach to data distribution management

Data distribution management (DDM) plays a key role in traffic control for large-scale distributed simulations. In recent years, several solutions have been devised to make DDM more efficient and adaptive to different traffic conditions. Examples of such systems include the region-based, fixed grid-based, and dynamic grid-based (DGB) schemes, as well as grid-filtered region-based and agent-based DDM schemes. However, less effort has been directed toward improving the processing performance of DDM techniques. This paper presents a novel DDM scheme called the adaptive dynamic grid-based (ADGB) scheme that optimizes DDM time through the analysis of matching performance. ADGB uses an advertising scheme in which information about the target cell involved in the process of matching subscribers to publishers is known in advance. An important concept known as the distribution rate (DR) is devised. The DR represents the relative processing load and communication load generated at each federate. The DR and the matching performance are used as part of the ADGB method to select, throughout the simulation, the devised advertisement scheme that achieves the maximum gain with acceptable network traffic overhead. If we assume the same worst case propagation delays, when the matching probability is high, the performance estimation of ADGB has shown that a maximum efficiency gain of 66% can be achieved over the DGB scheme. The novelty of the ADGB scheme is its focus on improving performance, an important (and often forgotten) goal of DDM strategies.     

Dynamic Grid-Based Approach to Data Distribution Management

Data distribution management (DDM) is one of the services defined by the DoD High Level Architecture and is necessary to provide efficient, scalable mechanisms for distributing state updates and interaction information in large scale distributed simulations. In this paper, we focus on data distribution management mechanisms (also known as filtering) used for real time training simulations. We propose a new method of DDM, which we refer to as the dynamic grid-based approach. Our scheme is based on a combination of a fixed grid-based method, known for its scalability, and a region-based strategy, which provides greater accuracy than the fixed grid-based method. We describe our DDM algorithm, its implementation, and report on the performance results that we have obtained using the RTI-Kit framework. Our results clearly indicate that our scheme is scalable and that it reduces the message overhead by 40%, and the number of multicast groups used by 98% when compared to the fixed grid-based allocation scheme using 10 nodes, 1000 objects, and 20,000 grid cells.     

一种基于网格的DDM区域匹配算法

在大规模分布式交互仿真中,数据分发管理(DDM)的重要功能是减少联邦成员接收不相关数据,实现数据过滤。它允许联邦成员在路径空间中通过更新区域或订购区域表达它们要发送或接收数据的范围,通过区域匹配运算确定数据供求关系,实现数据过滤。其关键是如何减少需要匹配的区域,以减少区域匹配运算量,文章以此为目的,提出一种基于网格的区域匹配算法。     

An Efficient Adaptive Transmission Control Scheme for Large-Scale Distributed Simulation Systems

Data distribution management (DDM) is one of the most critical component of any large-scale interactive distributed simulation systems. The aim of DDM is to reduce and control the volume of information exchanged among the simulated entities (federates) in a large-scale distributed simulation system. In order to fulfill its goal, a considerable amount of DDM messages needs to be exchanged within the simulation (federation). The question of whether each message should be sent immediately after it is generated or held until it can be grouped with other DDM messages needs to be investigated further. Our experimental results have shown that the total DDM time of a simulation varies considerably depending on which transmission strategy is used. Moreover, in the case of grouping, the DDM time depends on the size of the group. In this paper, we propose a novel DDM approach, which we refer to as Adaptive Grid-based (AGB) DDM. The AGB protocol is distinct from all existing DDM implementations, because it is able to predict the average amount of data generated in each time step of a simulation. Therefore, the AGB DDM approach controls a simulation running in the most appropriate mode to achieve a desired performance. This new DDM approach consists of two adaptive control parts: 1) the Adaptive Resource Allocation Control (ARAC) scheme and 2) the Adaptive Transmission Control (ATC) scheme. The focus of this paper is on the ATC scheme. We describe how to build a switching model to predict the average amount of DDM messages generated and how the ATC scheme uses this estimation result to optimize the overall DDM time. Our experimental results provide a clear evidence that the ATC scheme is able to achieve the best performance in DDM time when compared to all existing DDM protocols using an extensive set of experimental case studies.     

基于索引排序的快速动态区域匹配算法

数据分发管理实现基于值的过滤,可进一步减少大规模仿真中盟员接收冗余数据的可能性和网络中的数据流量.数据分发管理实现的关键是区域匹配算法的实现,高效、精确的区域匹配一直是数据分发管理追求的目标.现有的区域匹配算法如直接匹配法、网格法、基于分类的算法等都不很理想,或者过滤效果不佳,或者耗时较大,难以适应大规模分布式仿真的需要.论文针对在区域比较多的大规模分布式仿真系统中,区域大都需要随着仿真的推进而频繁地被动态修改的实际特点,提出了一个基于索引排序的快速动态区域匹配算法--IOBM算法,该算法将范围的上下界分别各用一个节点表示,使用指针数组来索引每一维上的范围节点,数组元素的下标值表示对应的节点值,利用区域范围更新前后的信息,将匹配限定在移动区间之内,通过对移动区间之内的链表进行直接操作来完成匹配工作,因而大大减少了匹配计算的时间,实现了高效、精确的动态匹配.该算法尤其适合区域比较多的大规模分布式仿真的需要.     

Scalability and Performance Evaluation of DDM-Based Aggregation/Dissaggregation Protocols for Large-Scale Distributed Interactive Simulations Systems

Aggregation/disaggregation is a method for implementing multi-resolution simulations within a High Level Architecture (HLA) federation. HLA is a U.S. Department of Defense (DoD) developed standard to facilitate linking different types of simulations, in various locations, to form an or interactive, full-scale simulation, called a federation. Data Distribution Management (DDM) is a High Level Architecture/Run-time Infrastructure (HLA/RTI) service that manages the distribution of state updates and interaction information and controls the volume of data exchanged, in large-scale distributed simulations. The purpose of HLA is to promote interoperability and reuse among heterogenous simulations, including those simulations that offer varied levels of resolution, to provide practical training to military personnel of different ranks. The purpose of Aggregation/disaggregation is to ensure consistency in state updates between federates simulating objects at various levels of resolution. This paper focuses on the scalability of aggregation/disaggregation with different DDM implementations and examines the effects, on performance of large-scale simulations. We implement a federate-based aggregation/disaggregation scheme, originally introduced in [TAN01], with a tank dogfight scenario, aggregating five tanks into one tank battalion and disaggregating the battalion back into five individual entities (tanks). The DDM methods we analyze consist of the Fixed Grid-Based method, the Dynamic Grid-Based method and the Region-Based method. In [TAN01], testing of this federate-based aggregation/disaggregation was limited to a dual federation and a single DDM scheme. In an effort to determine the scalability of aggregation/disaggregation, with three methods of DDM, we measure the communication overhead and analyze performance during a federation execution. We present the results of extensive testing, varying the number of aggregation/disaggregation requests, the number of multi-resolution federates participating in the federation, the number of objects, the number/size of the grids and report on the performance evlauation of our protocols using an extensive set of simulation experiments. This work was partially supported by Grants from NSERC, Canada Research Chairs Program, Canada Foundation for Innovation, OIT/Distinguished Researcher Award.     

基于位移残差的数据分发管理区域匹配及传输算法

高层体系结构(high level architecture,HLA)是建模与仿真的国际标准,它规定了数据分发管理服务(data distribution management,DDM)来减少不相关数据的发送与接收,从而减少网络带宽占用.发布区域与订购区域之间匹配计算的效率是影响数据分发管理服务质量的重要因素.区域信息的传输同样非常重要,盟员间通过区域信息的传输来保持区域的正确性和一致性,但区域信息的传输同样会给网络带来负载.现有算法通常是在区域保真度和网络负载两者之间做折中处理,难以兼顾。因此,本文充分考虑了变化区域的匹配效率以及区域传输的带宽占用问题,做出以下贡献:1)定义了区域变化与区域匹配变化之间的映射关系,采用该映射可以明显减少区域改变后所需要的匹配计算次数,从而提高了匹配效率;2)将区域更新信息划分为两种数据表达,区域快照与区域残差.通过尽量传输区域残差来代替传输完整的区域信息可以有效减少区域信息传输所消耗的网络带宽.因此,本文提出一种基于位移残差的DDM匹配与传输算法,给出了算法的理论分析与测试结果,并且对算法在实际应用中的表现进行了测试对比,给出了数据对比与结果分析.实验结果表明,基于位移残差的DDM匹配与传输算法具有良好的匹配效率,并且能够大大减少网络带宽占用,尤其是在具有大量不断变化区域的情况下.     

聚类的组播组分配策略在DDM中的实现

DDM(DataDistributionManagement)服务是高层体系结构HLA(HighLevelArchitecture)中定义的六大服务之一,它主要目的是通过减少网络间不相关数据的分发,提高网络的利用效率。一种常用的DDM优化方法是使用组播,组播是一种非常适合一对多的通信方式,它能够将更新数据发送到一个指定的定购者子集里。传统的DDM组播使用固定网格分配算法,在资源使用和数据发送方面存在一定的问题,不适合超大规模的仿真。本文在固定网格算法基础上提出了一种基于聚类的组播组分配算法,通过聚类,将固定网格的组播组进行合并,减少组播组的使用数量,提高网络资源的利用率,最后从实验结果上分析了聚类组播算法的优缺点。     

一种基于历史的DDM实现方法

DDM是HLA接口规范中定义的六大服务之一。它允许盟员声明其在路由空间中的更新区域和定购区域,从而达到减少HLA盟员间数据交换量的目的。它是RTI服务实现效率的关键,其核心问题是如何减少需要匹配的区域,以减少计算量。文章简要介绍了现有的几种方法,并分析了其各自的特点,在此基础上提出了一种基于历史的DDM方法。     

在HLA／DDM中多播组的分配方法

DDM是HLA接口规范中定义的六大服务之一,它允许邦员声明其在路由空间中的分布区域和定购区域,从而达到减少HLA邦员间数据交换量的目的。具体实现方法是数据过滤,其核心问题是如何将邦员中具有相似的公布区域或定购区域的对象聚集到一个多播组中。解决这个问题的传统方法是基于固定网络的方法,但该法存在一定缺陷。本文提出了
三种新的可选方法,并对这些方法的过滤效果和计算开销进行了评估。     

HLA/RTI中DDM小模型的实现

该文简要介绍了HLA中DDM存在的必要性 ,之后从一般分布式的观点分析了HLA及DDM实现的原理 ,同时给出了存在DDM的情况下 ,HLA中数据公布和订购的基本流程。最后介绍了DDM已知的实现方法和我们的实现方法 ,同时详细地给出了对象属性和交互的请求应答机制。     

大型分布交互式仿真系统的DDM策略研究

分布交互式仿真是未来仿真技术发展的方向.大型分布交互式仿真应用具有仿真实体数目较大、实体间信息交互频繁等特点,而分布仿真应用基于的网络带宽资源又十分有限,因此如何降低网络冗余数据,充分利用网络带宽资源以提高网络上的有效数据的传输效率成为一个重要的研究方向.数据分发管理DDM的目标是滤除仿真运行中网络上的无用数据,减少网络上的数据.文中简单地介绍了HLA的基本思想,阐述了路径空间的概念,并结合多目组通讯技术,描述了几种实用的DDM策略,比较了它们的异同点,为选用合适的数据滤除方法管理大型分布仿真的大规模数据提供了依据.     

一种基于跳表的DDM相交区域快速查询算法

HLA是为提高仿真系统的互操作性和可重用性而提出的新型分布仿真标准。HLA中数据分发管理服务的目的是通过邦员对数据公布和订购区域的表达来过滤一个邦员所接收到的数据,同时减少对网络带宽的消耗。DDM的核心是多维矩形区域动态相交查找的问题,其算法性能的好坏对DDM的效率是至关重要的。现有的一些动态区域查找算法还不能同时满足高效、精确且易于实现等要求,为此设计出一种基于跳表数据结构的用于快速相交区域查找的区问跳表,同时分析了区间跳表的构造原则以及基本操作的流程,并在此基础上提出了基于区间跳表的相交区域查找算法。该算法的匹配精度高,时间复杂度低,且具有编程实现简单的特点。     

基于动态R-树结构的DDM区域匹配算法

分析了传统数据分发管理(DDM)匹配方法,结合空间索引技术的特点,提出了一种动态R-树区域匹配方法,通过建立R-树对公布和订购区域进行组织管理,并在R-树上实现订购区域与公布区域的匹配搜索。仿真实验结果表明,选取适当参数M,可减少动态R-树DDM匹配算法的时间开销,达到较优性能。     

分布式虚拟现实中数据分发管理算法研究

分布式虚拟现实（Distributed Virtual Reality,DVR）系统具有仿真实体数目较大,实体间信息交互频繁等特点,现有的网络带宽资源又十分有限,因此如何降低网络冗余数据,充分利用网络带宽资源及提高网络上有效数据的传输速率成为一个重要的研究方向。因此,结合分布式虚拟现实中数据的特点,利用IEEE 1516标准-高层体系结构HLA（HighLevel Architecture）对分布式虚拟现实中的数据分发管理（Data distributed Management,DDM）算法进行研究。     

DDM中基于历史信息排序的区域匹配算法

DDM实现的关键是更新区域和订购区域的匹配判断,其匹配算法的设计决定着分布式仿真的效率和性能。 针对直接匹配算法需要维护的区域相交索引表和相交信息表的存储空间不断扩大的问题,首先提出区域聚合的基本 思想及其实现方式,然后提出将历史信息排序加入到区域匹配算法中,以使算法在有效利用历史信息的基础上,提高 区域匹配的运行效率。给出了算法的基本思想和具体步骤,通过应用实例详细解释了算法的具体实现过程,最后通过 仿真实验,对比分析了所提算法的优缺点。     

A near-wall strategy for buoyancy-affected turbulent flows using stabilized FEM with applications to indoor air flow simulation

We consider the numerical simulation of buoyancy-affected, incompressible turbulent flows using a stabilized finite-element method. We present an approach which combines two domain decomposition methods (DDM). Firstly, we apply a DDM with full overlap for near-wall modelling, which can be interpreted as an improved wall-function concept. Secondly, a non-overlapping DDM of iteration-by-subdomains-type for the parallel solution of the linearized problems is employed. For this scheme, we demonstrate both the accuracy for a benchmark problem and the applicability to realistic indoor-air flow problems.     

分布交互仿真中基于Server的层次过滤机制

大规模分布交互仿真对网络带宽、处理资源等提出了很高的要求,采用数据过滤机制可大大降低对网络带宽和计算资源的压力,有利于系统可扩性.然而对于高效过滤机制,仿真结点机要接收和处理足够的过滤信息.当系统规模增大时,大量过滤信息交换和处理占用了过多的计算资源,影响了正常的仿真任务.该文提出了一种基于Server的层次化过滤机制,解决了仿真节点计算能力受限的问题.同时,新的机制利用仿真的内在局部性,开发了两级过滤信息,从而减少了Server内部过滤信息计算量.     

分布仿真中的兴趣管理研究进展

兴趣管理机制通过数据过滤和数据分发技术，使得仿真实体在仿真过程中能够荻取计算所需的相关数据，又不会被与计算无关的报文所淹没，是提高分布仿真系统性能和扩展能力的关键技术。本文对目前采用的兴趣管理机制进行了回顾，分析了相应的特点，并结合当前的发展趋势，阐述了目前研究的热点。