research-article

A dynamic sort-based DDM matching algorithm for HLA applications

Authors:

Stephen John Turner,

Zengxiang LiAuthors Info & Claims

ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 21, Issue 3

Article No.: 17, Pages 1 - 17

https://doi.org/10.1145/1921598.1921601

Published: 04 February 2011 Publication History

Abstract

Simulation is a low-cost and safe alternative to solve complex problems in various areas. To promote reuse and interoperability of simulation applications and link geographically dispersed simulation components, distributed simulation was introduced. The High-Level Architecture (HLA) is the IEEE standard for distributed simulation. To optimize communication efficiency between simulation components, HLA defines a Data Distribution Management (DDM) service group for filtering out unnecessary data exchange. It relies on the computation of overlap between update and subscription regions, which is called “matching”. There are many existing matching algorithms, among which a sort-based approach improves efficiency by sorting region bounds before the actual matching process, and is found to outperform other existing matching algorithms in many situations. However, the existing algorithm performs matching for all regions in one round and cannot dynamically deal with a selective region modification without processing all the regions once again. Realizing that in many spatial applications, only a small subset of all regions are actually modified in each time step, this article proposes a dynamic sort-based matching algorithm to deal with this efficiently. Theoretical analysis has been carried out for the proposed algorithm and experimental results show that the proposed algorithm has significantly better performance than major existing matching algorithms at dynamic matching.

References

[1]

Ayani, R., Moradi, F., and Tan, G. 2000. Optimizing cell-size in grid-based DDM. In Proceedings of the 14th Workshop on Parallel and Distributed Simulation. 93--100.

Digital Library

[2]

Bassiouni, M., Chiu, M. H., Loper, M., and Garnsey, M. 1998. Relevance filtering for distributed interative simulation. Comput. Syst. Sci. Eng. 13, 1, 39--47.

[3]

Bentley, J. L. and Wood, D. 1980. An optimal worst case algorithm for reporting intersections of rectangles. IEEE Trans. Computers 29, 7, 571--577.

Digital Library

[4]

Boukerche, A. and Dzermajko, C. 2003. Alternative approaches to data distribution management in large-scale distributed simulation systems. In Proceedings of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems. 555--562.

[5]

Boukerche, A., Mcgraw, N. J., and Araujo, R. B. 2005. A grid-filtered region-based approach to support synchronization in large-scale distributed interactive virtual environments. In Proceedings of the International Conference on Parallel Processing Workshops. 525--530.

Digital Library

[6]

Cohen, J. D., Lin, M. C., Manocha, D., and Ponamgi, M. K. 1995. I-collide: An interactive and exact collision detection system for large-scale environments. In Proceedings of the Symposium on Interactive 3D Graphics. 189--196.

Digital Library

[7]

DMSO. 2002. High Level Architecture RTI 1.3NG Programmer's Guide. Version 6.

[8]

Fujimoto, R. M. 2000. Parallel and Distributed Simulation Systems. Wiley Interscience.

Digital Library

[9]

Hyett, M. and Wuerfel, R. 2002. Implementation of the data distribution management services in the RTI-NG. In Proceedings of the Spring Simulation Interoperability Workshop. Paper 02S-SIW-044.

[10]

IEEE. 2000. Standard 1516 (HLA Rules), 1516.1 (Federate Interface Specification), and 1516.2 (Object Model Template).

[11]

Kalashnikov, D. V., Prabhakar, S., and Hambrusch, S. E. 2004. Main memory evaluation of monitoring queries over moving objects. Int. J. Distrib. Parall. Datab. 15, 2, 117--135.

Digital Library

[12]

Liu, E. S., Yip, M. K., and Yu, G. 2005. Scalable interest management for multidimensional routing space. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology. 82--85.

Digital Library

[13]

Liu, E. S., Yip, M. K., and Yu, G. 2006. Lucid platform: Applying HLA DDM to multiplayer online game middleware. ACM Comput. Entertain. 4, 4. Article 9.

Digital Library

[14]

Morse, K. L. and Petty, M. D. 2001. Data distribution management migration from DoD 1.3 to IEEE 1516. In Proceedings of the 5th IEEE International Workshop on Distributed Simulation and Real Time Applications. 58--65.

Digital Library

[15]

Morse, K. L. and Steinman, J. S. 1997. Data distribution management in the HLA multidimensional regions and physically correct filtering. In Proceedings of the Spring Simulation Interoperability Workshop. Paper 97S-SIW-052.

[16]

Pan, K., Turner, S. J., Cai, W., and Li, Z. 2007. An efficient sort-based DDM matching algorithm for HLA applications with a large spatial environment. In Proceedings of the 21st ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation. 70--82.

Digital Library

[17]

Petty, M. D. 2000. Geometric and algorithmic results regarding HLA data distribution management matching. In Proceedings of the Fall Simulation Interoperability Workshop. Paper 00F-SIW-072.

[18]

Petty, M. D. and Morse, K. L. 2004. The computation complexity of the High Level Architecture Data Distribution Management matching and connecting processes. Simul. Model. Pract. Theor. 12, 3--4, 217--237.

[19]

Petty, M. D. and Mukherjee, A. 1997. Experimental comparison of d-rectangle intersection algorithms applied to HLA data distribution. In Proceedings of the Fall Simulation Interoperability Workshop. Paper 07F-SIW-016.

[20]

Prabhakar, S., Xia, Y., Kalashnikov, D. V., Aref, W. G., and Hambrusch, S. E. 2002. Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects. IEEE Trans. Comput. 51, 10, 1124--1140.

Digital Library

[21]

Raczy, C., Tan, G., and Yu, J. 2005. A sort-based DMM matching algorithm for HLA. ACM Trans. Model. Comput. Simul. 15, 1, 14--38.

Digital Library

[22]

Rak, S. J. and Van Hook, D. J. 1996. Evaluation of grid-based relevance filtering for multicast group assignment. In Proceedings of the 14th Distributed Interactive Simulation Workshop, 739--747.

[23]

Tan, G., Ayani, R., Zhang, Y., and Moradi, F. 2000. Grid-based data management in distributed simulation. In Proceedings of the 33rd Annual Simulation Symposium. 7--13.

Digital Library

[24]

Tan, G., Zhang, Y., and Ayani, R. 2000. A hybrid approach to data distribution management. In Proceedings of the 4th IEEE International Workshop on Distributed Simulation and Real-Time Applications. 55--61.

Digital Library

[25]

Tao, Y., Papadias, D., and Sun, J. 2003. The TPR&ast;-tree: An optimized spatio-temporal access method for predictive queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 790--801.

Digital Library

[26]

Van Hook, D. J. and Calvin, J. O. 1998. Data distribution management in RTI 1.3. In Proceedings of the Spring Simulation Interoperability Workshop.

[27]

Wood, D. D. 2002. Implementation of DDM in the MAK high performance RTI. In Proceedings of the Spring Simulation Interoperability Workshop. Paper 02S-SIW-056.

[28]

Yu, X., Pu, K. Q., and Koudas, N. 2005. Monitoring k-nearest neighbor queries over moving objects. In Proceedings of the 21st Internationnal Conference on Data Engineering (ICDE'05). 631--642.

Digital Library

Cited By

Tang WYao YOu LChen K(2024)Hierarchical sort-based parallel algorithm for dynamic interest matchingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104867188:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104867
Karaca Oİmre KAlkar A(2023)Network accelerator for parallel discrete event simulationsThe Journal of Supercomputing10.1007/s11227-023-05365-279:16(18728-18747)Online publication date: 19-May-2023
https://dl.acm.org/doi/10.1007/s11227-023-05365-2
Tang WYao YZhu FChen BCai WDiallo STolk AGiabbanelli P(2021)A Parallel Hierarchical Sort-based Interest Matching AlgorithmProceedings of the 2021 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3437959.3459259(107-118)Online publication date: 21-May-2021
https://dl.acm.org/doi/10.1145/3437959.3459259
Show More Cited By

Index Terms

A dynamic sort-based DDM matching algorithm for HLA applications

Recommendations

A sort-based DDM matching algorithm for HLA

The High Level Architecture (HLA) is an architecture for reuse and interoperation of simulations. It provides several Data Distribution Management (DDM) services to reduce the transmission and reception of irrelevant data. These services rely on the ...
An Efficient Sort-Based DDM Matching Algorithm for HLA Applications with a Large Spatial Environment
PADS '07: Proceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation

Simulation is a low cost and safe alternative to solve complex problems in various areas. To promote reuse and interoperability of simulation applications and link geographically dispersed simulation components, distributed simulation was introduced. ...
Moving-intersecting-information-based matching algorithm for dynamic DDM
SCSC '09: Proceedings of the 2009 Summer Computer Simulation Conference

The HLA Data Distribution Management (DDM) service provides value-based data filtering capability to reduce the transmission and reception of irrelevant data. The performance of DDM relies strongly on the computation of the intersection between update ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation

ACM Transactions on Modeling and Computer Simulation Volume 21, Issue 3

March 2011

141 pages

ISSN:1049-3301

EISSN:1558-1195

DOI:10.1145/1921598

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 February 2011

Accepted: 01 August 2010

Revised: 01 August 2010

Received: 01 February 2010

Published in TOMACS Volume 21, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
336
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tang WYao YOu LChen K(2024)Hierarchical sort-based parallel algorithm for dynamic interest matchingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104867188:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104867
Karaca Oİmre KAlkar A(2023)Network accelerator for parallel discrete event simulationsThe Journal of Supercomputing10.1007/s11227-023-05365-279:16(18728-18747)Online publication date: 19-May-2023
https://dl.acm.org/doi/10.1007/s11227-023-05365-2
Tang WYao YZhu FChen BCai WDiallo STolk AGiabbanelli P(2021)A Parallel Hierarchical Sort-based Interest Matching AlgorithmProceedings of the 2021 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3437959.3459259(107-118)Online publication date: 21-May-2021
https://dl.acm.org/doi/10.1145/3437959.3459259
Petty M(2021)An Empirical Study of the Effect of Reducing Matching Frequency in High-Level Architecture Data Distribution ManagementAdvances in Parallel & Distributed Processing, and Applications10.1007/978-3-030-69984-0_71(975-990)Online publication date: 19-Oct-2021
https://doi.org/10.1007/978-3-030-69984-0_71
Marzolla MD'Angelo G(2020)Parallel Data Distribution Management on Shared-memory MultiprocessorsACM Transactions on Modeling and Computer Simulation10.1145/336975930:1(1-25)Online publication date: 5-Feb-2020
https://dl.acm.org/doi/10.1145/3369759
Li TYao YTang WYao FZhu F(2019)An exponential search enhanced dynamic sort-based interest matching algorithm for interest management in distributed simulationSimulation Modelling Practice and Theory10.1016/j.simpat.2019.04.009Online publication date: Apr-2019
https://doi.org/10.1016/j.simpat.2019.04.009
Neal SFujimoto R(2017)Energy consumption of HLA data distribution management approachesProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242243(1-11)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242243
Marzolla MD'Angelo GGarro AD'Ambrogio A(2017)Parallel sort-based matching for data distribution management on shared-memory multiprocessorsProceedings of the 21st International Symposium on Distributed Simulation and Real Time Applications10.5555/3199858.3199860(1-8)Online publication date: 18-Oct-2017
https://dl.acm.org/doi/10.5555/3199858.3199860
Neal SFujimoto R(2017)Energy consumption of HLA data distribution management approaches2017 Winter Simulation Conference (WSC)10.1109/WSC.2017.8247834(810-820)Online publication date: Dec-2017
https://doi.org/10.1109/WSC.2017.8247834
Marzolla MD'Angelo G(2017)Parallel sort-based matching for data distribution management on shared-memory multiprocessors2017 IEEE/ACM 21st International Symposium on Distributed Simulation and Real Time Applications (DS-RT)10.1109/DISTRA.2017.8167660(1-8)Online publication date: Oct-2017
https://doi.org/10.1109/DISTRA.2017.8167660
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents