A Hybrid HLA Time Management Algorithm Based on Both Conditional and Unconditional Information

ABSTRACT

The High Level Architecture (HLA), which is the IEEE standard for distributed simulation, defines six service groups. The Time Management (TM) service group ensures a Time-Stamp-Ordered (TSO) message delivery sequence and correct time advancement of each simulation component (federate) in an HLA-based distributed simulation application (federation). To control time advancement of a federation, a distributed TM algorithm requires each regulating federate to periodically propagate its local time information to all constrained federates for their respective calculation of Greatest Available Logical Time (GALT). The time information propagated is called conditional information or unconditional information depending on whether it can be guaranteed to be true conditionally or unconditionally. A traditional distributed TMalgorithm can be either synchronous or asynchronous. In general, a synchronous algorithm utilizes conditional information while an asynchronous algorithm utilizes unconditional information. However, both synchronous and asynchronous algorithms have their own drawbacks and thus cannot be used for all federation scenarios. To resolve the drawback of each algorithm, this paper proposes a hybrid TM algorithm by combining synchronous and asynchronous algorithms. The three algorithms have been incorporated into an RTI (Run Time Infrastructure) and experimental results show that the hybrid algorithm effectively combines the advantages of both synchronous and asynchronous algorithms.

REFERENCES

• 1: R. E. Bryant. Simulation of packet communication archi tecture computer systems. Master's thesis, Massachusetts Institute of Technology, 1977.
• 2: Christopher D. Carothers , Richard M. Fujimoto , Richard M. Weatherly , Annette L. Wilson, Design and implementation of HLA time management in the RTI version F.0, Proceedings of the 29th conference on Winter simulation, p.373-380, December 07-10, 1997, Atlanta, Georgia, United States [doi>10.1145/268437.268511]
• 3: K. M. Chandy , J. Misra, Distributed Simulation: A Case Study in Design and Verification of Distributed Programs, IEEE Transactions on Software Engineering, v.5 n.5, p.440-452, September 1979 [doi>10.1109/TSE.1979.230182]
• 4: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 5: R. M. Fujimoto. Lookahead in parallel discrete event simulation. In International Conference on Parallel Processing, Volume 3, pages 34-41, 1988.
• 6: R. M. Fujimoto. Time management in the high level architecture. SIMULATION Special Issue on High Level Architecture , 71(6):388-400, 1998.
• 7: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 8: Richard Fujimoto , Thom McLean , Kalyan Perumalla , Ivan Tacic, Design of High Performance RTI Software, Proceedings of the Fourth IEEE International Workshop on Distributed Simulation and Real-Time Applications, p.89, August 25-27, 2000
• 9: Globus Alliance. Globus Toolkit Version 4. Available via http://www.globus.org/.
• 10: IEEE. Standard 1516 (HLA Rules), 1516.1 (Federate Interface Specification) and 1516.2 (Object Model Template), 2000.
• 11: David M. Nicol, The cost of conservative synchronization in parallel discrete event simulations, Journal of the ACM (JACM), v.40 n.2, p.304-333, April 1993 [doi>10.1145/151261.151266]
• 12: K. Pan, S. J. Turner, W. Cai, and Z. Li. A service oriented HLA RTI on the Grid. In International Conference on Web Services, pages 984-992, 2007.
• 13: Behrokh Samadi, Distributed simulation, algorithms and performance analysis (load balancing, distributed processing), University of California, Los Angeles, 1985
• 14: J. Steinman. SPEEDES: Synchronous parallel environment for emulation and discrete event simulation. In Advances in Parallel and Distributed Simulation, pages 95-103, 1991.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance

Keywords:
Distributed Simulation, HLA, Time Management Algorithm