Aggregate Level Simulation Protocol

The Aggregate Level Simulation Protocol (ALSP) is a protocol and supporting software that enables simulations to interoperate with one another. Replaced by the High Level Architecture (simulation) (HLA), it was used by the US military to link analytic and training simulations.

ALSP consists of:

ALSP Infrastructure Software (AIS) that provides distributed runtime simulation support and management;
A reusable ALSP Interface consisting of generic data exchange message protocols; and
Participating simulations adapted for use with ALSP.

History

In 1990, the Defense Advanced Research Projects Agency (DARPA) employed The MITRE Corporation to study the application of distributed interactive simulation principles employed in SIMNET to aggregate-level constructive training simulations. Based on prototype efforts, a community-based experiment was conducted in 1991 to extend SIMNET to link the US Army's Corps Battle Simulation (CBS) and the US Air Force's Air Warfare Simulation (AWSIM). The success of the prototype and users' recognition of the value of this technology to the training community led to development of production software. The first ALSP confederation, providing air-ground interactions between CBS and AWSIM, supported three major exercises in 1992.

By 1995, ALSP had transitioned to a multi-Service program with simulations representing the US Army (CBS), the US Air Force (AWSIM), the US Navy (RESA), the US Marine Corps (MTWS), electronic warfare (JECEWSI), logistics (CSSTSS), and intelligence (TACSIM). The program had also transitioned from DARPA's research and development emphasis to mainstream management by the US Army's Program Executive Office for Simulation, Training, and Instrumentation (PEO STRI)

Contributions

ALSP developed and demonstrated key aspects of distributed simulation, many of which were applied in the development of HLA.

No central node so that simulations can join and depart from the confederation at will
Geographic distribution where simulators can be distributed to different geographic locations yet exercise in the same simulated environment
Object ownership so each simulation controls its own resources, fires its own weapons and determines appropriate damage to its systems when fired upon
A message-based protocol for distributing information from one simulation to all other simulations.
Time management so that the times for all simulations appear the same to users and so that event causality is maintained – events should occur in the same sequence in all simulations.
Data management permits all simulations to share information in a commonly understood manner even though each had its own representation of data. This includes multiple simulations controlling attributes of the same object.
An architecture that permits simulations to continue to use their existing architectures while participating in an ALSP confederation.

Motivation

In 1989, the Warrior Preparation Center (WPC) in Einsiedlerhof, Germany hosted the computerized military exercise ACE-89. The Defense Advanced Research Projects Agency (DARPA) used ACE-89 as a technology insertion opportunity by funding deployment of the Defense Simulation Internet (DSI). Its packetized video teleconferencing brought general officers of NATO nations face-to-face during a military exercise for the first time; this was well received. But the software application of DSI, distribution of Ground Warfare Simulation (GRWSIM), was less successful. The GRWSIM simulation was unreliable and its distributed database was inconsistent, degrading the effectiveness of the exercise.

DARPA was funding development of a distributed tank trainer system called SIMNET where individual, computerized, tank-crew trainers were connected over local area networks and the DSI to cooperate in a single, virtual battlefield. The success of SIMNET, the disappointment of ACE-89, and the desire to combine existing combat simulations prompted DARPA to initiate research that lead to ALSP.

Basic Tenets

DARPA sponsored the design of a general interface between large, existing, aggregate-level combat simulations. Aggregate-level combat simulations use Lanchestrian models of combat rather than individual physical weapon models and are typically used for high-level training. Despite representational differences, several principles of SIMNET applied to aggregate-level simulations:

Dynamic configurability. Simulations may join and depart an exercise without restriction.
Geographic distribution. Simulations can reside in different geographic locations yet exercise over the same logical terrain.
Autonomous entities. Each simulation controls its own resources, fires its own weapons and, when one of its objects is hit, conducts damage assessment locally.
Communication by message passing. A simulation uses a message-passing protocol distribute information to all other simulations.

The ALSP challenge had requirements beyond those of SIMNET:

Simulation time management. Typically, simulation time is independent of wall-clock time. For the results of a distributed simulation to be "correct," time must be consistent across all simulations.^[1]
Data management. The schemes for internal state representation differ among existing simulations, necessitating a common representational system and concomitant mapping and control mechanisms.
Architecture independence. Architectural characteristics (implementation language, user interface, and time flow mechanism) of existing simulations differed. The architecture implied by ALSP must be unobtrusive to existing architectures.

Conceptual Framework

A conceptual framework is an organizing structure of concepts that facilitates simulation model development.^[2] Common conceptual frameworks include: event scheduling, activity scanning and process interaction.

The ALSP conceptual framework is object-based where a model is composed of objects that are characterized by attributes to which values are assigned. Object classes are organized hierarchically in much the same manner as with object-oriented programming languages. ALSP supports a confederation of simulations that coordinate using a common model.

To design a mechanism that permits existing simulations to interact, two strategies are possible: (1) define an infrastructure that translates between the representations in each simulation, or (2) define a common representational scheme and require all simulations to map to that scheme.

The first strategy requires few perturbations to existing simulations; interaction is facilitated entirely through the interconnection infrastructure. However, this solution does not scale well. Because of an underlying requirement for scalability, the ALSP design adopted the second strategy. ALSP prescribes that each simulation maps between the representational scheme of the confederation and its own representational scheme. This mapping represents one of the three ways in which a simulation must be altered to participate in an ALSP confederation. The remaining modifications are:

Recognizing that the simulation doesn't own all of the objects that it perceives.
Modifying the simulation's internal time advance mechanism so that it works cooperatively with the other simulations within the confederation.

In stand-alone simulations, objects come into (and go out of) existence with the passage of simulation time and the disposition of these objects is solely the purview of the simulation. When acting within a confederation, the simulation-object relationship is more complicated.

The simulation-object ownership property is dynamic, i.e. during its lifetime an object may be owned by more than one simulation. In fact, for any value of simulation time, several simulations may own different attributes of a given object. By convention, a simulation owns an object if it owns the "identifying" attribute of the object. Owning an object's attribute means that a simulation is responsible for calculating and reporting changes to the value of the attribute. Objects not owned by a particular simulation but within the area of perception for the simulation are known as ghosts. Ghosts are local copies of objects owned by other simulations.

When a simulation creates an object, it reports this fact to the confederation to let other simulations create ghosts. Likewise, when a simulation deletes an object, it reports this fact to enable ghost deletion. Whenever a simulation takes an action between one of its objects and a ghost, the simulation must report this to the confederation. In the parlance of ALSP, this is an interaction. These fundamental concepts provide the basis for the remainder of the presentation. The term confederation model describes the object hierarchy, attributes and interactions supported by a confederation.

ALSP Infrastructure Software (AIS)

The object-based conceptual framework adopted by ALSP defines classes of information that must be distributed. The ALSP Infrastructure Software (AIS) provides data distribution and process coordination. Principal components of AIS are the ALSP Common Module (ACM) and the ALSP Broadcast Emulator (ABE).

ALSP Common Module (ACM)

The ALSP Common Module (ACM) provides a common interface for all simulations and contains the essential functionality for ALSP. One ACM instance exists for each simulation in a confederation. ACM services require time management and object management; they include:

Coordinate simulations joining and departing from a confederation..
Coordinate simulation local time with confederation time.
Filter incoming messages, so that simulations receive only messages of interest.
Coordinate ownership of object attributes, and permit ownership migration.
Enforce attribute ownership so that simulations report values only for attributes they own.

Time management

Joining and departing a confederation is an integral part of time management process. When a simulation joins a confederation, all other ACMs in the confederation create input message queues for the new simulation. Conversely, when a simulation departs a confederation the other ACMs delete input message queues for that simulation.

ALSP time management facilities support discrete event simulation using either asynchronous (next-event) or synchronous (time-stepped) time advance mechanisms.^[3] The mechanism to support next-event simulations is

A simulation sends an event-request message to its ACM with a time parameter corresponding to simulation time T, (the time of its next local event).
If the ACM has messages for its simulation with timestamps older than or the same as T, the ACM sends the oldest one to the simulation. If all messages have timestamps newer than T, the ACM send a grant-advance to the simulation, giving it permission to process its local event at time T.
The simulation sends any messages resulting from the event to its ACM.
The simulation repeats from step (1).

The mechanism to support time-stepped simulation is:

The simulation processes all events for some time interval $(T,T+?T]$ .
The simulation sends an advance request to its ACM for time $T+?T$ .
The ACM sends all messages with time stamps on the interval $(T,T+?T]$ to the simulation, followed by a grant-advance to T+?T.
The simulation sends any messages for the interval $(T,T+?T]$ to the ACM.
The simulation repeats from step (1).

AIS includes a deadlock avoidance mechanism using null messages. The mechanism requires that the processes have exploitable lookahead characteristics.

Object management

The ACM administers attribute database and filter information. The attribute database maintains objects known to the simulation, either owned or ghosted, and attributes of those objects that the simulation currently owns. For any object class, attributes may be members of

Create set. Attributes minimally required to represent an object
Interest set. Useful, but not mandatory, information
Update set. Object attribute values reported by a simulation to the confederation

Information flow across the network can be further restricted through filters. Filtering provides discrimination by (1) object class, (2) attribute value or range, and (3) geographic location. Filters also define the interactions relevant to a simulation.

If (an update passes all filter criteria)
|  If (the object is known to the simulation)
|  |  Send new attribute values to simulation
|  Else (object is unknown)
|  |  If (enough information is present to create a ghost)
|  |  |  Send a create message to the simulation
|  |  Else (not enough information is known)
|  |  |  Store information provided
|  |  |  Send a request to the confederation for missing data
Else (the update fails filter criteria)
|  If (the object is known to the simulation)
|  |  Send a delete message to the simulation
|  Else 
|  | Discard the update data

The ownership and filtering information maintained by the ACM provide the information necessary to coordinate the transfer of attribute ownership between simulations.

ALSP Broadcast Emulator (ABE)

An ALSP Broadcast Emulator (ABE) facilitates the distribution of ALSP information. It receives a message on one of its communications paths and retransmits the message on all of its remaining communications paths. This permits configurations where all ALSP components are local to one another (on the same computer or on a local area network). It also permits configurations where sets of ACMs communicate with their own local ABE with inter-ABE communication over wide area networks.

Communication Scheme

The ALSP communication scheme consists of (1) an inter-component communications model that defines the transport layer interface that connects ALSP components, (2) a layered protocol for simulation-to-simulation communication, object management, and time management, (3) a message filtering scheme to define the information of interest to a simulation, and (4) a mechanism for intelligent message distribution.

Inter-component Communications Model

AIS employs a persistent connection communications model^[4] to provide the inter-component communications. The transport layer interface used to provide inter-component communications was dictated by simulation requirements and the transport layer interfaces on AIS-supporting operating systems: local VMS platforms used shared mailboxes; non-local VMS platforms used either Transparent DECnet or TCP/IP; and UNIX-like platforms use TCP/IP.

ALSP Protocol

The ALSP protocol is based on a set of orthogonal issues that comprise ALSP's problem space: simulation-to-simulation communication, object management, and time management. These issues are addressed by a layered protocol that has at the top a simulation protocol with underlying simulation/ACM, object management, time management, and event distribution protocols.

Simulation Protocol

The simulation protocol is the main level of the ALSP protocol. It consists of four message types:

Update. Objects in ALSP are defined by a unique id number, a class, and a set of attributes associated with a c1ass. As a simulation changes the state its objects, it sends update messages to the ACM that provide initial or changed attribute values. The ACM then distributes the information via AIS to other simulations in that have indicated interest.
Interaction. Interactions between objects are identified by kind. Interaction kinds are described by parameters, just as objects are described by attributes. When a simulation's object engages either another simulation's object or a geographic area, the simulation sends an interaction message to the ACM for further dissemination to other interested simulations.
Refresh request. A simulation can request an update of a set of attribute values for any object or class of objects by sending a refresh request message to the confederation.
Delete. When a simulation causes one of its objects to cease to exist, the simulation sends a delete message to inform other simulations.

The simulation protocol is text-based. It is defined by an LALR( 1) context-free grammar. The semantics of the protocol are confederation-dependent, where the set of classes, class attributes, interactions, and interaction parameters are variable. Therefore, the syntactical representation of the simulation protocol may be defined without a priori knowledge of the semantics of the objects and interactions of any particular confederation.

Simulation/ACM Connection Protocol

The simulation/ACM connection protocol provides services for managing the connection between a simulation and its ACM and a method of information exchange between a simulation and its ACM. Two services control distribution of simulation protocol messages: events and dispatches. Event messages are time-stamped and delivered in a temporally-consistent order. Dispatch messages are delivered as soon as possible, without regard for simulation time. Additional protocol messages provide connection state, filter registration, attribute lock control, confederation save control, object resource control, and time control services.

Object Management Protocol

The object management protocol is a peer-level protocol that sits below the simulation protocol and provides object management services. ACMs solely use it for object attribute creation, acquisition, release, and verification (of the consistency of the distributed object database). These services allow AIS to manage distributed object ownership.

Distributed object ownership presumes that no single simulation must own all objects in a confederation, but many simulations require knowledge of some objects. A simulation uses simulation protocol update messages to discover objects owned by other simulations. If this simulation is interested in the objects, it can ghost them (track their locations and state) and model interactions to them from owned objects.

Locks implement attribute ownership. A primary function of the object management protocol is to ensure that a simulation only updates attributes for which it has acquired a lock. The object manager in the ACM manages the objects and object attributes of the owned and ghosted objects known to the ACM. Services provided by the simulation/ACM protocol are used by the simulations to interact with the ACM's attribute locking mechanism. The coordination of status, request, acquisition, and release of object attributes, between ACMs, uses the object management protocol. Each attribute of each object known to a given ACM has a status that assumes one of three values:

Locked. A simulation controls the attribute and may update the attribute value. A simulation "owns" the attribute if it has that attribute locked. A simulation "owns" the object if it has its id attribute locked.
Unlocked. No simulation currently controls the attribute. Any simulation asking for control is granted control.
Gone. The state of control is held elsewhere in the confederation.

From the ACM's perspective, objects come into existence through the registration process performed by its simulation or through the discovery of objects registered by other simulations. The initial state attribute locks for registered objects and discovered objects is as follows:

Object Registration places each object-attribute pair in the locked state. The simulation may optionally specify attributes to be in the unlocked state.
Object Discovery adds an object to the object database as a ghosted object. All of the attributes for this object are marked with a status of gone.

Time Management Protocol

The time management protocol is also a peer-level protocol that sits below the simulation protocol. It provides time management services for synchronizing simulation time among ACMs. The protocol provides services for the distributed coordination of a simulation's entrance into the confederation, time progression, and confederation saves.

The join/resign services and time synchronization mechanisms are described in Section earlier. The save mechanism provides fault tolerance. Coordination is required to produce a consistent snapshot of all ACMs, translators and simulations for a particular value of simulation time.

Message Filtering

The ACM uses simulation message filtering to evaluates the content of a message received from the confederation. The ACM delivers messages to its simulation that are of interest, and pass filtering criteria and discards those that are not of interest. The ACM filters two types of messages: update messages and interaction messages.

Update messages. The ACM evaluates update messages based on the simulation's update message filtering criteria that the simulation provides. As discussed in earlier, when an ACM receives an update message there are four possible outcomes: (1) the ACM discards the message, (2) the ACM sends the simulation a create message, (3) the ACM sends the simulation the update message, or (4) the ACM sends the simulation a delete message.

Interaction messages. An ACM may discard interaction messages because of the kind parameter. The kind parameter has a hierarchical structure similar to the object class structure. The simulation informs its ACM of the interaction kinds that should pass or fail the interaction filter.

Message Distribution

To minimize message traffic between components in an ALSP confederation, AIS employs a form of intelligent message routing that uses the Event Distribution Protocol (EDP).^[5] The EDP allows ACMs to inform the other AIS components about the update and interaction filters registered by their simulations. In the case of update messages, distribution of this information allows ACMs to only distribute data on classes (and attributes of classes) that are of interest to the confederation. The ABE also use this information to send only information that is of interest to the components it serves. For interaction messages, the process is similar, except that the kind parameter in the interaction message determines where the message is sent.

References

^ Lamport, L. (1978). "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, 21(7), pp. 558-565, July.
^ Balci, O., Nance, R.E., Derrick, E.J., Page, E.H. and Bishop, J.L. (1990). "Model Generation Issues in a Simulation Support Environment," In: Proceedings of the 1990 Winter Simulation Conference, pp. 257-263, New Orleans, LA, 9–12 December.
^ Nance, R.E. (1971). "On Time Flow Mechanisms for Discrete Event Simulations," Management Science, 18(l), pp. 59-93, September.
^ Boggs, D.R. Shoch, J.F., Taft, E.A., and Metcalfe, R.M. (1979). "PUP: An Internetwork Architecture," Report CSL-79- 10, XEROX Palo Alto Research Center, July.
^ Weatherly, R.M., Wilson, A.L. and Griffin, S.P. (1993). "ALSP - Theory, Experience, and Future Directions," In: Proceedings of the 1993 Winter Simulation Conference, pp. 1068-1072, Los Angeles, CA, 12–15 December.

[lamport-1] Lamport, L. (1978). "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, 21(7), pp. 558-565, July.

[balci-2] Balci, O., Nance, R.E., Derrick, E.J., Page, E.H. and Bishop, J.L. (1990). "Model Generation Issues in a Simulation Support Environment," In: Proceedings of the 1990 Winter Simulation Conference, pp. 257-263, New Orleans, LA, 9–12 December.

[nance-3] Nance, R.E. (1971). "On Time Flow Mechanisms for Discrete Event Simulations," Management Science, 18(l), pp. 59-93, September.

[boggs-4] Boggs, D.R. Shoch, J.F., Taft, E.A., and Metcalfe, R.M. (1979). "PUP: An Internetwork Architecture," Report CSL-79- 10, XEROX Palo Alto Research Center, July.

[Weatherly-5] Weatherly, R.M., Wilson, A.L. and Griffin, S.P. (1993). "ALSP - Theory, Experience, and Future Directions," In: Proceedings of the 1993 Winter Simulation Conference, pp. 1068-1072, Los Angeles, CA, 12–15 December.

[1]

[2]

[3]

[4]

[5]