Distributed Interactive Simulation In the Legion Environment

Adam J. Ferrari (ferrari@virginia.edu)

University of Virginia

Abstract

In this paper, we examine the Legion metasystem, a project whose goal is to provide a general purpose software framework and design paradigm for the development of large scale distributed systems. In particular, we examine Legion's applicability to one of the highest priority software development efforts of the U.S. government: Distributed Interactive/Interoperable Simulation(DIS). The potential benefits of a DIS-over-Legion implementation are numerous, addressing a number of the software complexity and scalability issues inherent in the DIS objectives. Furthermore, the development of Legion based solutions to the basic scalability problems in DIS would have direct, immediate benefits in many other application domains. Thus, we propose that DIS be implemented over the Legion system.

I. Introduction

The area of large scale distributed systems and applications is currently at a crossroad between revolution and evolution. While some view the Information Superhighway and National Information Infrastructure (NII) as an embellishment of the Internet, others subscribe to a wider vision. The existing and potential computation and information resources in the U.S. alone are nothing short of breathtaking. As yet, these resources have largely remained separate "islands of service" connected for simple applications such as electronic mail and file transfer, but the distributed application domain is expanding rapidly. Distributed parallel computing environments (e.g. PVM [15]), automated collaboration and telepresence tools (e.g. MBONE [4]), simulation and training platforms (e.g. DIS [11]), and large scale distributed databases and file systems [10] are just a few examples of this growing area. As is often the case, the needs of an expanding application domain create a demand for the development of underlying technologies and standards. In this paper, we examine the Legion metasystem [8][9], a project whose goals address these needs. In particular, we shall examine Legion's applicability to one of the highest priority software development efforts of the U.S. government: Distributed Interactive/Interoperable Simulation (DIS) [3].

The scope of the Legion project is at the nation- and world-wide level. Its basic goal is to present a single, seamless "virtual machine" computing environment to geographically distributed users which will enable easy access to high performance computing, enhanced ability to collaborate on information-oriented projects (e.g. research, education, training), and the development of a coherent set of tools for distributed computing. This would be a welcome change to users who have become accustomed to the often confusing, mismatched set of ad-hoc tools which comprise the realm of distributed computing today.

Like Legion, DIS is a project of global proportions. The stated goal of DIS is to provide a general purpose interactive distributed simulation system capable of supporting all phases and aspects of simulations of thousands to millions of heterogeneous entities on hardware dispersed around the world [11]. This is no small goal, exacting serious requirements on network, processing, management, and development technologies. It seems unlikely that this will be achieved without the firm organizational framework provided by a software infrastructure like Legion.

II. Overview of DIS

The use of geographically distributed computing resources in the training, readiness enhancement, and evaluation of the armed forces is not a novel idea. For example, the SIMNET [1] project successfully enabled the virtual simulation of armored vehicle engagements and is still the basis of much work on DIS today. Furthermore, constructive simulations employed by the various branches of the armed forces (e.g. Corps Battle Simulation (CBS), Air War Simulation (AWSIM)) have been successfully merged in a distributed environment using the Aggregate Level Simulation Protocol (ALSP). The DIS project is unique in its broad intended domain of applicability. While the current usage of DIS is primarily intended to serve the armed forces, the resulting technology is fully intended to meet the needs of real-time simulationists in a wide range of areas [2]. Given the great potential for advancement in so many fields provided the ability to perform realistic simulations on the DIS scale, it is hard to overestimate the importance of the role that DIS will play in the future.

II.A. Background and Objectives

The list of DIS objectives is almost as impressive in its scope as the simulation domains in which DIS is intended to be utilized. These goals [2] [3][11] [12][13] include:

This set of goals sets forth a challenging array of technological requirements. The basic compute cycle and network bandwidth/latency requirements alone push the limits of current technology. Despite this, it seems clear that the challenge introduced by the DIS objectives is that of software complexity management. Unfortunately, this is the area in which the current implementation of DIS is most lacking.

II.B. Current Status

The current implementation of DIS shares many common features with its SIMNET ancestor, but also adds a number of important developments. In many cases, however, the current DIS incarnation does not fully address the the issues raised above. The central theme of the DIS architecture is the Protocol Data Unit (PDU), a message packet of fixed length which defines the common communication medium of DIS entities. PDUs are broadcast over a hierarchical, heterogeneous network designed to meet the bandwidth and latency requirements associated with DIS. To reduce these requirements to reasonable levels, entities in DIS are required to adhere to certain algorithmic policies such as remote entity approximation (REA). REA and related schemes (e.g. dead reckoning) are simply methods to trade off network usage for higher computational costs. Beyond these minimal requirements, essentially any software which can be made to communicate via PDUs can participate in a DIS simulation.

At current, this scheme is adequate. DIS can be viewed as an evolutionary effort to build on the success of SIMNET. In fact, in the realm of a SIMNET-like world (tank warfare), the DIS community is addressing many significant technological issues surrounding the accurate simulation of armored vehicle warfare. For example, work in progress is aimed at representing dynamic terrain features, incorporating intelligent use of multicast technology, and allowing military simulations at the constructive level to participate in DIS exercises. These will certainly be significant improvements to the current DIS system, but they only begin to scratch the surface of the larger DIS vision.

To achieve the lofty objectives of the DIS vision, nothing short of a software revolution will be required. The current SIMNET-like DIS protocol does not enforce semantic consistency. Entities are dubbed "interoperable" simply because they utilize similar network packets. Furthermore, DIS does not provide any long-term solution to the problem of software complexity management. Even in the short to medium term, the cost in time and money to develop DIS software entities will become unacceptable. Finally, DIS fails to address the issues of performing simulations not related to military agendas. This shortcoming is bound to lead to a great deal of wasted investment given the obvious applicability of DIS technology to other areas. Consider the areas of economic modeling, weather simulation, entertainment, and commercial transportation training. It seems likely that a more general domain of support could only serve to improve the state of military simulation [14].

Clearly, a methodology beyond the current ad-hoc development of DIS is required. This leads us to our examination of Legion.

III. The Legion MetaSystem

III.A. Background and Objectives

The current state of distributed computing tools is in many ways in turmoil. For example, a group of researchers collaborating on a problem via MBONE whiteboard, audio and video tools must employ an entirely different tool/protocol (e.g. ftp, gopher) if they wish to exchange files. If they need to find recent or archived on-line information relating to their topic of interest, they are yet again faced with an array of choices (e.g. World Wide Web/Mosaic, wais). If their local computing environments employ differing data representations, they must explicitly employ a separate translation tool (e.g. XDR). Clearly, a unified environment could potentially offer more than the sum of the current set of ad-hoc tools in terms of productivity and simplicity. That unified environment will be Legion.

The overall goal of Legion is to provide a single, seamless, large scale distributed computing environment to users and application developers. The primary driving objectives behind the Legion effort include:

These goals are certainly non-trivial. Given the large set of distributed computing tools in common use already, however, we see that many pieces of the puzzle already exist. The missing element is a logical, cohesive, sophisticated software infrastructure. The availability of computing power in distributed systems has already been demonstrated using low level systems such as PVM [18], while the information wealth on distributed systems is only beginning to be fully realized through metasystems [6] such as the World Wide Web. Given the current wealth of tools for distributed computing, Legion will implement the next logical step, concentrating on the following themes:

III.B. System Architecture

The goals discussed in III.A will be realized through a system architecture incorporating the technical objectives described above. The framework of the Legion architecture is centered on the concept of object-oriented design principles [16]. The merits of object-oriented software engineering have been heavily examined in recent years, and it is considered a solid design scheme leading to the encapsulation and management of complexity, the convenient expression of abstraction and relationships, and the re-use of software components. Because of these attributes, object-oriented design is central to the Legion architecture.

The software development starting point for Legion is the Mentat object-oriented, high performance parallel computing system [7]. Mentat combines a virtual machine software layering scheme with object-oriented parallelism encapsulation to achieve high performance and an easy to use, C++ based programming environment. From Mentat, Legion inherits its object based interface and inherent ability to exploit parallelism. While Mentat (and similarly Legion) does not automatically parallelize code, it does substantially reduce the complexity of creating parallel applications by providing higher level programming models.

In Legion, all entities known to the system are objects. Objects belong to classes (which are themselves objects) from which they inherit attributes, methods, and interfaces. All objects are addressed in the Legion system by a unique identification number. Access to an object is via its class interface, which describes all of the possible actions (methods) which can affect the object. These methods are specified using an interface description language (IDL). The attributes of an object class, including its interface, scheduling requirements, and other data are dynamically available from a distributed class description database(CDD), thus facilitating programmer usage of a potentially enormous set of classes.

Objects can assume different states. For example, a code object might be in abstract (source) or concrete (executable) form. Similarly, given the prospect of millions of objects available in the system, executable objects might be active or dormant. Some objects may be labeled as persistent, in which case they must have a saved state if dormant. The management of the objects in the Legion system and their different object states is performed by the Legion Object Management System (OMS). Besides state management, the OMS is also responsible for scheduling objects based on class scheduling constraints and the current system load. The Legion system attempts to schedule objects on suitable resources in order to minimize the total execution time [6].

Given that all Legion entities are defined as objects, it seems natural to wonder if existing applications will have a place in Legion. Legion will provide tools to create object "wrappers" for these legacy codes, allowing them to be fully interoperable with normally defined Legion objects. These existing applications can be sequential in nature (e.g. part of years of investment in Fortran code), or might be parallel (e.g. using the PVM portability platform). Through the use of automated tools and libraries, these applications will be able to interact with Legion facilities using the appropriate Legion object interface protocol.

The naming of objects is based on a three level scheme. At the lowest level, each object can have a location and state dependent address. For example, on a Unix-based workstation connected to the system via IP, the low level object address of an active object might be a combination of the host IP number, Unix process-id, and UDP port number for that object. At the next highest level is the Legion object-id, which is a unique id-number associated with each object in the system. Since these raw bit-string ids will certainly be inconvenient at the user interface level, a high level naming scheme will be employed to map string names to Legion object-ids. This string name mapping will be performed in a distributed fashion by name-server objects. The operation of this distributed naming scheme will be sensitive to the environment of the user. For example, one user may want the string "tmp" mapped to one object, while another user may want the same string mapped to a different object.

Executable objects, whether legacy or native Legion codes, consume resources. Naturally, since individual organizations subscribe their personal resources to Legionaire status, resource usage accounting is provided. While the Legion resource usage accounting scheme has direct application to, for example, billing and load throttling, it can also be used for program analysis. For example, one might wish to determine the message volume into a given object during the execution of a program.

Thus far, we have focussed attention on objects as computational entities. As mentioned, objects may be persistent in nature and thus can also represent persistent data (e.g. files, databases). As a user-level service, a federated file system is under development which will take advantage of these Legion services and provide system-wide access to objects similar in nature to Unix files. Other, more complex object classes are also under development which will replicate persistent data for performance and fault tolerance purposes, or provide structured, persistent data stores which can be correctly accessed by machines of different data representations transparently.

Naturally, given the unified name space containing executable and persistent objects, security is a major concern in Legion. The security mechanism proposed for Legion is based on a ticket based scheme. Objects have associated user-defined (or conservative default) "may I" methods which return non-transferable tickets redeemable for services from an object. The ticket dispensing policy may be based on requester identification, object type, or any other available information. Once a ticket is provided (in encrypted form), it must accompany any method invocations on the granting object in order for an object to receive service. Clearly, this security scheme can not make up for security holes in the underlying operating system. The Legion philosophy in light of this is to "do no harm" by not providing additional opportunities for security breaches.

III.C. Current Status

The current prototype version of Legion is being implemented at the University of Virginia under the title the "Campus-wide Virtual Computer" (CWVC). Thus far, the foundations have been constructed to realize a fair subset of the system architecture in an extended Mentat environment. At current, the process of developing applications to operate in the CWVC environment is in progress with the intent of demonstrating the utility of the Legion model. Some applications are already in production use in the Legion environment. These include applications in biochemistry, electrical engineering, and atmospheric simulation. Once the development of the CWVC is complete, the process of moving Legion to the nation-wide scale will begin.

IV. DIS Over Legion

We have now examined the basic elements of a high-level, large scale distributed metasystem, Legion, and a large-scale, demanding distributed application, DIS. The task remains to explore the applicability of the Legion model to the DIS application domain. As may seem evident by this point, Legion is in many ways a solid framework in which to construct a truly general, scalable distributed interactive simulation system. Similarly, DIS is exactly the type of challenging application whose heavy demands could serve to drive Legion technology forward. Thus, we now examine the potential benefits and challenges of a DIS implementation over Legion.

IV.A. Points in Favor

Object-oriented design provides a framework to model at various levels of abstraction. For example, a high level-abstract object class might describe the common attributes of an airplane (e.g. wingspan, maximum air-speed). More detailed simulation entities could then be derived from this common airplane class, and could then concentrate on implementing only the details which make the derived entity unique (e.g. special weapons systems, surveillance equipment). Many of these added details could themselves be existing object class building blocks. For example, two different planes might be armed with the same missile. The results of such a design scheme would be increased semantic consistency, re-use of code, and encapsulation of complexity. These issues have a direct impact on the scalability of the system. By making it easier and cheaper to construct new entities, the simulation may become scalable to whatever dimensions and domains are required.

First, configuration and control of simulations can be logically centralized [14], providing convenient tools with which new simulations could be efficiently created, and running simulations modified. The unified, coherent data store would also facilitate the creation of a logically centralized "library" of simulation base classes, tools and objects [14]. This would be a great step into the realm of potential semantic consistency. For example, separate developers would not be likely to construct airplane entity simulators with widely different interfaces, capabilities, and semantic assumption if they were encouraged to save time and money by re-using the same air vehicle base-class object.

As a final note regarding the unified, coherent data-space provided by Legion, such a service would clearly provide a means through which VV&A could be realized. The needs of V&V engineers include the ability to trace the simulation development process from concept design, through software construction and testing. This information intensive activity would be greatly simplified by Legion's unified data-space in concert with its natural collaboration environment.

Perhaps some of the greatest benefits of parallel performance are envisionable in the simulation development and analysis phases. In the developmental stages, parallelism could be the key to the efficient creation of large scale simulation databases (e.g. terrain data). The computation-heavy analysis phase could also be made more efficient through parallelism, leading to quicker access to simulation results, and subsequently quicker development of the next set of simulation goals.

First, DIS entities are by definition intended to be executed on heterogeneous hardware entities. Legion's support of this heterogeneity would prevent the tight coupling of entity software and its intended hardware platform (except of course in the case of specialized simulation hardware). Furthermore, the automatic mapping of entity software to appropriate hardware could help further the real-time cause of DIS, assuming that the initial cost of scheduling was not prohibitive.

IV.B. Challenges

Despite all of the clear benefits for the DIS application domain in a Legion environment, the transition to the Legion paradigm would not be simple for DIS. Similarly, while the intended scope and services provided by Legion match the apparent requirements of DIS, it is not unlikely that DIS would pose some technological challenges for Legion.

One such conflict between DIS and Legion revolves around the object communication models employed by each. Legion provides methods as the interface through which objects interact, but does not directly support the 1-to-n, n-to-1, and n-to-n communication patterns employed by DIS. While Legion doesn't "prohibit" a separate communication medium/model, such a structure would clearly violate the intent and nullify a number of the possible Legion benefits. Fortunately, the shortcoming in Legion with respect to support of different communication patterns (for example, as required by data-parallel application) has been identified and is an area of active research.

A further challenge for a DIS implementation over Legion is Legion's lack of real-time guarantees. The current DIS implementation requires real-time guarantees from its underlying network architecture. While the available network resources would remain unchanged for a Legion DIS implementation, Legion would naturally involve some software overheads. The potential for integrating real time services into Legion or implementing such services over Legion would be an important area of further investigation related to a DIS implementation in Legion.

Another potential challenge to DIS-over-Legion lies in the level of interest in DIS already translated into development activities. DIS-over-Legion would represent a fundamental shift in orientation. Naturally, a good deal of inertia and resistance would be expected. It is our hope that this paper will provide a starting point for demonstrating that DIS will be significantly easier and more cost-effective to develop in Legion, thus overcoming much of this hesitance.

A final challenge we shall enumerate here is also a result of the great interest in DIS, especially on the part of the government. Given the successes already achieved by DIS, the pressures to move the development of DIS forward are quite substantial. The DoD has put forth a very ambitious research agenda / development schedule for DIS [3]. Since Legion is not yet fully developed, the short term goals of the DIS development schedule would pose a serious challenge to DIS-over-Legion. On the other hand, Legion would greatly improve the chances of achieving the long term DIS development goals.

V. Conclusion

The idea of a general purpose, large scale distributed simulation tool such as DIS in a Legion environment is compelling and certainly warrants further exploration. DIS as it exists today is an important, quickly expanding application area of distributed computing, yet it is in many ways fundamentally flawed. As we have seen, many of the flaws and shortcomings of DIS are addressed quite nicely in Legion.

Naturally, any pairing of DIS and Legion would involve many technical and organizational challenges. Taken in perspective however, these challenges seem relatively small compared to the dangers involved in constructing a system of DIS proportions in an ad-hoc fashion. Furthermore, the result of an effort to construct DIS-over-Legion could have many secondary benefits. The broad spectrum of requirements to implement DIS properly contains many sub-areas which need to be addressed in a variety of distributed applications. For example, consider distributed medicine. How different are the distributed computing requirements of this field from those of DIS?

Thus, as certainly as DIS would benefit from employing Legion as a software framework, Legion could benefit from the wear and tear and developmental challenges of a large scale application which encompasses many of the requirements of a wide range of distributed computing problem domains. Such an implementation effort could help decide the question of revolution or evolution for a variety of areas in distributed computing. If the NII is to fulfill its promise, such challenges must be undertaken.

Acknowledgments

I would like to thank Paul Reynolds for running an excellent seminar in distributed simulation last fall. This paper is largely due to discussion and insights shared within that seminar group. I would also like to thank my advisor, Andrew Grimshaw, for helping me understand the Legion vision. I would also like to thank Sudhir Srinivasan and Anh Nguyen-Tuong for their helpful comments on the paper, and Michele Ierardi for her editing skills.

Bibliography

  1. Bolt, Beranek, and Bewman Incorporated, "The SIMNET Network and Protocols," BBN Laboratories Report No. 6787, May 1988.
  2. DIS Steering Commmittee, "The DIS Vision, A Map to the Future of Distributed Simulation," Institute for Simulation and Training, October 1993.
  3. DoD Directive (DoDD) 5000.59-P, "Modeling and Simulation Master Plan," 30 September 1994.
  4. Hans Eriksson, "MBONE: The Multicast Backbone" Communications of the ACM, Vol.37, No.8, pp. 54--60, August 1994.
  5. Richard M. Fujimoto, "Parallel Discrete Event Simulation," Communications of the ACM, Vol.33, No.10, pp. 30--53, October 1990.
  6. A.S. Grimshaw, J.B. Weissman, E.A. West, E. Loyot Jr., "MetaSystems: An Approach Combining Parallel Processing and Heterogeneous Distributed Computing Systems," University of Virginia, Computer Science CS-92-43, 1992.
    ftp://uvacs.cs.virginia.edu/pub/techreports/CS-92-43.ps.Z
  7. A.S. Grimshaw, W.T. Strayer, P. Narayan, "Dynamic, Object-Oriented Parallel Processing," IEEE Parallel & Distributed Technology, pp. 33--47, May 1993.
  8. A.S. Grimshaw, W.A. Wulf, J.T. French, A.C. Weaver, and P.F. Reynolds Jr., "A Synopsis of the Legion Project," University of Virginia, Computer Science CS-94-20, 1994.
    ftp://uvacs.cs.virginia.edu/pub/techreports/CS-94-20.ps.Z
  9. A.S. Grimshaw, W.A. Wulf, J.T. French, A.C. Weaver, and P.F. Reynolds Jr., "Legion: The Next Logical Step Toward a Nationwide Virtual Computer," University of Virginia, Computer Science CS-94-21, 1994.
    ftp://uvacs.cs.virginia.edu/pub/techreports/CS-94-21.ps.Z
  10. E.Levy and A. Silberschatz, "Distributed File Systems: Concepts and Examples," ACM Computing Surveys, vol.22, No.4, pp.321--374, December, 1990.
  11. Loral Systems Company, "Strawman Distributed Interactive Simulation Architecture Description," Vol.1, Advanced Distributed Simulation Technology Program Office, Orlando, FL, March 1992.
  12. Loral Systems Company, "Strawman Distributed Interactive Simulation Architecture Description: Supporting Rationale - Time/Space Coherence and Interoperability," Vol.2, Book 1, Advanced Distributed Simulation Technology Program Office, Orlando, FL, March 1992.
  13. Loral Systems Company, "Strawman Distributed Interactive Simulation Architecture Description: Supporting Rationale - DIS Architecture Issues," Vol.2, Book 2, Advanced Distributed Simulation Technology Program Office, Orlando, FL, March 1992.
  14. Paul F. Reynolds, Jr., "DISorientation", Elecsim'94, Electronic Conference, May 1994.
  15. V. S. Sunderam, "PVM: A Framework for Parallel Distributed Computing," Concurrency: Practice and Experience, Vol.2, No.4, pp. 315--339, December 1990.
  16. Bjarne Stroustrup, "What is Object-Oriented Programming?" IEEE Software, May 1988.
  17. D.R. Wallace, R.U. Fujii, "Software Verification and Validation: An Overview," IEEE Software, May 1989.
  18. S. White, A. Alund, V.S. Sunderam, "Performance of the NAS Parallel Benchmarks on PVM Based Networks," Emory University, Computer Science RNR-94-008, May 1994.
    ftp://mathcs.emory.edu/pub/vss/nasapvm1.ps.Z