1.0 INTRODUCTION

A goal of the HLA is appropriate support for all types of DoD simulations. Because a diverse collection of simulation types must be supported, the RTI data distribution services must be efficient and flexible. Efficiency requires that the RTI mechanisms and interfaces be suited to scaling of simulations from very small to very large along many dimensions including numbers of simulated objects, complexity of interactions, fidelity of representations, and computational/network resources. Flexibility requires that the RTI mechanisms and interfaces not be tied to any particular problem domain or technology but instead be general in nature. Simultaneous requirements for efficiency and flexibility are often difficult to satisfy and solutions that address either or both must also be tempered by economic realities.

Data distribution in the DIS protocols and architecture has been for the most part broadcast, i.e., updates and interactions are routed from each producing simulation to all other simulations. Irrelevant information is generally discarded at the receiving simulations in order to reduce local processing loads. This results in obvious inefficiencies: local processing resources are consumed to filter out irrelevant data; network resources are consumed to deliver data that will only be thrown away. For small scale simulations such waste is relatively unimportant. However, the DIS broadcast scheme becomes unworkable as exercises increase beyond a relatively small size.

These scaling problems have been addressed in various ways as part of a number of recent programs and demonstrations including STOW-E (Synthetic Theater Of War - Europe) [4], STOW RITN (Realtime Information Transfer and Networking) [5,6], and JPSD (Joint Precision Strike Demonstration) [7]. Common characteristics shared to a greater or lesser extent by these approaches include:

• Multicast addressing to route all relevant data and minimal irrelevant data from producers to consumers.
  
• Expression of data interests.
  
• Hierarchical filtering.
  
• Hierarchical architecture.

2.0 ROUTING SPACES

Subscription regions define a subset of a routing space and specify the data that a federate wishes to receive. Update regions also define a subset of a routing space and specify data that a federate offers to produce and send. The RTI determines which federates need to receive data from which other federates by detecting when senders' update regions overlap with receivers' subscription regions in a routing space.

Figure 1: Update (U1) and subscription (S1, S2) regions defined in a two dimensional routing space.

A federation may define multiple routing spaces, each with different characteristics and employed for different purposes. The following information must be agreed on by the federation members to use a routing space:

• The number of dimensions.
  
• A variable corresponding to each dimension, termed a routing variable.
  
• The mapping of the routing variables to routing space coordinates.

The number of dimensions may vary from one up to a maximum value limited only by the RTI implementation and the underlying technology. There is no conceptual limit to the number of dimensions in a routing space. This permits arbitrarily complex filtering to be specified via routing spaces.

Each dimension has a routing variable identified with it by the federation. Routing variables may be attributes such as the scalar temperature. Components of attributes may also be chosen as routing variables. For example, each of the three components of a vector location attribute (e.g., latitude, longitude, and altitude) may be selected as routing variables for the dimensions of a three dimensional routing space. Routing variables may also be functions of an attribute or attributes. For example, speed, calculated as the magnitude of a vector velocity attribute could be selected as a routing variable. Routing variables are not even required to be attributes or be derived from attributes. Any data item that a federation agrees on can be used as a routing variable (e.g., IP subnet address).

In addition to the number of dimensions in a routing space and the routing variables corresponding to each dimension, a federation must agree on the mapping from routing variables expressed in federation units and data types to routing space coordinates. This mapping requires a federation to agree on the minimum and maximum values of each routing variable along with an arbitrary mapping function. The simplest mapping function is of course a linear mapping but the federation may agree to use an arbitrary function of its choice.

3.0 HLA INTERFACE TO DATA DISTRIBUTION MANAGEMENT SERVICES

void CreateUpdateRegion (
  in SpaceHandle,
  in ExtentSet,
  out Region)
void CreateSubscriptionRegion (
  in SpaceHandle,
  in ExtentSet,
  out Region)
void deleteRegion (
  in Region)

void subscribeObjectClassAttribute (
  in ObjectClassHandle,       
  in AttributeHandle,   
  in Region)      
void subscribeInteractionClass (
  in InteractionClassHandle,
  in Region)

void associateUpdateRegion (
  in Region,
  in ObjectId,
  in AttributeHandleSet)
void associateUpdateRegion (
  in Region,
  in InteractionClassHandle)
void disassociateUpdateRegion (
  in Region,
  in ObjectId)
void disassociateUpdateRegion (
  in Region,
  in InteractionClassHandle)

The association formed by these services can be thought of as a contract between the federate and the RTI. The federate agrees to ensure that the characteristics of the object or interaction which map to the dimensions of the update region fall within the extents of that region. If not, the object's attributes either need to be associated with a different region or the extents of the region must be modified to reflect the new object state. For its part, the RTI agrees to deliver associated attributes and interactions to relevant subscribers.

void modifyRegion (
  in Region,
  in ExtentSet)

void changeThresholds (
  in Region,
  out ThresholdSet)

4.0 PROTOTYPE RTI FRAMEWORK FOR DATA DISTRIBUTION MANAGEMENT SERVICES

• Separation of routing and forwarding
  
• Use of agents and hierarchical architecture
  
• Hierarchical filtering

4.1 Routing vs. Forwarding

4.2 Agents to Facilitate Scalability

The RTI data distribution framework uses subscription agents to manage federates' expressions of interest and to determine the necessary network connectivity. Each federate communicates its data interests, expressed in terms of classes, attributes, and routing space regions, to a subscription agent. Subscription agents cooperate to determine the connectivity needed to forward data from producers to consumers. The RITN program constructed and successfully tested a subscription agent as part of STOW Engineering Demonstration 1A [5,6]. The RITN subscription agent calculated multicast groups based on its client simulations' dynamic subscriptions and publications.

For small simulation systems or simple connectivity algorithms, each federate has its own subscription agent executing locally. Larger simulation systems requiring more interaction or computation may employ a subscription agent for collections of federates, e.g., a subscription agent per local area network.

4.3 Hierarchical Filtering

There are three opportunities for filtering in a simulation system: at sources, in the network via routing, and at receivers. There are different cost tradeoffs involved in each of these. For example, filtering at receivers (after data has been received) requires only a broadcast capability from the network infrastructure and little sophisticated routing capability but lots of computation at receivers as exercise scale grows. On the other hand, source filtering (sending data only if another simulation needs it) requires relatively sophisticated protocols to inform senders about whether any other simulation has subscribed for particular data. A third alternative, filtering via the network infrastructure, requires a multicasting capability or emulation of multicasting (e.g., via exploders). Such approaches can yield greatly enhanced scalability as demonstrated by the STOW RITN program [5,6].

The RTI supports all aspects of hierarchical filtering. At the source, a federate can be directed by the RTI to not send particular attributes and/or interactions. The approaches described in Section 5 support exploiting capabilities of the network infrastructure to route only relevant data to receivers. Finally, the RTI filters received data based on a hierarchy of tests that include filtering on:

• Destination address.
  
• Class and attribute names.
  
• Update region. The RTI can optionally discard received messages based on update region extents included in each message. This capability provide the ability to do exact filtering despite quantization effects of some connectivity algorithms as described in Section 5.

4.4 Data Distribution Framework

Express interest. Interest is expressed by each federate to the RTI for the data to be sent and received. Interest is specified as subscription and update regions in routing spaces together with classes and attributes. Federates communicate their interest to subscription agents.

Cluster. Clustering reduces the number of regions that must be manipulated by combining subscription regions together and combining update regions together. Regions in routing spaces may be clustered (coalesced, combined, unified) by a number of different algorithms. This reduces communication and computation costs related to matching. Clustering is performed by subscription agents.

Match. Matching compares update regions with subscription regions to determine overlap in the routing space. Attributes and interactions associated with update regions must be received by federates whose subscription regions overlap with update regions. Matching produces a list of destination federates for each update region. Such a receiver list may be empty in which case the data associated with that update region need not be forwarded or even calculated in the first place. That data is relevant to no other federate.

Establish connectivity. Network connectivity is established based on sets of receiving federates resulting from matching update and subscription regions. An example of such connectivity is a set of multicast groups.

Transfer data. Attributes and interactions are transferred from producers to consumers using the connectivity that has been established. All relevant data, as determined from matching of clustered subscription and update regions, is relayed to appropriate receivers. As little irrelevant data as possible is routed from senders to receivers.

Figure 2: RTI Data Distribution Framework.

An important question is how best to represent regions so that they may be efficiently clustered and efficiently matched. A number of approaches applicable to representing spatial regions are described in [10]. A good compromise between factors such as storage, computational cost, complexity, and generality is afforded by the multidimensional equivalent of a binary tree data structure. In two dimensions this is called a quadtree, in three an octtree.

Clustering of regions in routing spaces using multidimensional binary trees is illustrated in Figures 3 and 4. Figure 3 shows a two dimensional routing space with two regions in it denoted R1 and R2. For purposes of this example, the maximum depth of the tree is two so that no further partitioning beyond that shown in the lower right hand quadrant is permitted. Children of nodes are denoted 0, 1, 3, and 2 starting from the upper left quadrant and proceeding in a counter clockwise direction. A leaf node is denoted in this example by referencing the sequence of nodes traversed from the root to the leaf. For example, the bottom right child of the bottom right child of the root node is designated 3­3.

Figure 3: Illustration of clustering of regions in a routing space using multidimension binary trees.

Multidimensional binary tree data structures can be very efficiently represented by a set of integer codes that cluster or combine together individual regions inserted in a tree. Such codes reference nodes in the tree and hierarchically define clusters of regions. The code representing the clustering of the regions in our simple quadtree example can be reported as "3." This references the lower right child node of the root. This represents both region R1 and region R2.

Matching consists of efficient mask and compare operations on arrays of integer codes representing subscription regions and update regions clustered via multidimensional binary trees.

Figure 4: Depiction of the quadtree data structure for the regions and routing space in Figure 3.

5.0 APPROACHES AND ANALYSIS

The analysis reported in this paper has been performed on log files collected during the STOW RITN ED1A exercise. ED1A consisted of an week long intensive test of the RITN scalability and network infrastructure during which a large body of network traffic was logged. The test scenarios were predominantly ground engagements of between several hundred to more than five thousand simulated entities generated by ModSAF running on 62 workstations. The workstations were distributed across seven LANs at NRL, NRaD, TEC, IDA, and University of Texas ARL. These sites were connected by a multicasting ATM WAN. Further details about the RITN architecture and the ED1A experiment are found in [5,6]. The data reported in this paper were taken from a scenario consisting of approximately 2000 entities and a little over thirty minutes duration.

Figure 5: Total packet rates delivered to simulators at the NRaD 156 LAN for various filtering algorithms. STOW ED1A Run 2.1 of 14 November 1995.

Figure 6: Total packet rates delivered to simulators at the NRaD 156 LAN for receiver-based filtering and various quadtree depths. STOW ED1A Run 2.1 of 14 November 1995.

Figure 5 shows the total packet rate delivered to the eleven workstations located at one of the two NRaD LANs over the course of the scenario. The top trace shows the broadcast traffic that would have been delivered to the workstations (the sum over all the workstations) had no filtering algorithms been used. The bottom trace shows ideal traffic flows. Ideal traffic was calculated by post processing logger data to determine what traffic needed to flow between host computers based upon the viewing ranges of the simulated entities. Viewing ranges of four kilometers and ten kilometers for ground and air vehicles were used, respectively.

The broadcast and ideal traces form a useful set of bounds for comparing the effectiveness of other filtering techniques that we wish to evaluate. Three additional classes of techniques (grid-based, receiver-based, and sender based) will be described and preliminary measures of their performance presented in the following sections. Each of these techniques supports the routing space abstraction, programming interface, and data distribution framework described in previous sections of this paper.

5.1 Grid-Based Filtering

• Subdivide each routing space into an array of cells and assign a multicast group to each cell.
  
• Determine which cells overlap each subscription region and join the groups assigned to those cells.
  
• Determine which cells overlap each update region and send updates for attributes and interactions associated with an update region to the groups assigned to the overlapping cells.
  
• Federates receive data sent to groups they have joined (relevant data) but do not receive data sent to groups they have not joined (irrelevant data).

Figure 7 illustrates the grid approach. In this example, a two dimensional routing space is configured to have four cells along one dimension and three along the other. A federate specifies a subscription region S1 and joins groups 1­3, 5­7, and 9­11. Attributes and interactions associated with update regions U1 and U2 are sent to groups 10 and 9, respectively and delivered to the federate that specified S1. Attributes and interactions associated with U3 are sent to group 4 but are not delivered to the subscribing federate.

Figure 7: Illustration of grid-based filtering showing pairing of groups with cells and matching of update regions (U1, U2, U3) and subscription regions (S1) via a grid.

The simplicity of grid approaches makes them attractive. They are relatively easy to implement and robust because they require no interaction between agents for senders and receivers to establish connectivity. Matching of subscription and update regions is performed implicitly on a grid local to both the senders and receivers. Only the number of cells in each dimension and the algorithm for assigning multicast groups to cells must be shared. Clustering is not absolutely necessary because interest regions need not be communicated nor is mapping of subscription and update regions to grid cells a particularly compute intensive operation.

Despite these good features, grid approaches have a number of drawbacks that make them inadequate or unacceptable for many applications. These include:

• Large numbers of groups may be needed if the number of routing spaces and routing space dimensions is at all large. Multicast groups tend to be a scarce resource whose over use has performance implications in the network infrastructure and in host I/O performance. Use of a larger number of groups also implies an increase in group change rate with more bursty traffic profiles as an undesirable consequence [14].
  
• Multiple transmissions may be required for extended update regions that are not points in routing space (one for each grid overlapped by the update region) or excessively large interest extents, thereby reducing efficiency. While most vehicles and individual combatants can be adequately dealt with by point update regions, some simulated objects are inherently volumetric. Examples include weather, smoke, dust, electromagnetics, nuclear, chemical, and biological effects.
  
• No explicit use of information about what data is relevant is exploited, making grid approaches suboptimal. Data is sent even if it is relevant to no other federate. Also, the number of groups used can be in excess of what is actually needed provide the necessary connectivity. This is because senders have no idea what receivers are listening vice versa.
  
• Irrelevant data is delivered because of the inherent quantization of the grid. Addressing this problem by reducing the grid size (increasing the number of cells along any routing space dimension) can vastly increase multicast group usage. In the RTI prototype, update regions are included in each update to permit irrelevant data to be optionally discarded through filtering at the receivers.

Overall, grid approaches are adequate for applications that do not need to push the limits of scalability, performance, and cost. Relative ease of implementation induced the RTI development team to select a grid approach as the initial approach in the RTI prototype. But better approaches are needed to achieve the required scalability of simulation systems supported by the RTI.

5.2 Receiver-Based Filtering

In receiver-based filtering, subscription agents cluster each federates' subscription regions and update regions and communicate the clustered subscription regions to other subscription agents. Each agent matches its local update regions with subscription regions from other agents to determine a set of receiver federates. The matching operation produces lists of federates to which data associated with each update region must be delivered. Multicast groups providing the necessary connectivity are determined for each update region. Attributes and interactions are transmitted using these groups. As the update regions or subscription regions change the connectivity is incrementally recalculated. A number of approaches are possible for determining what multicast groups to use for each update region. These approaches range from fully static at one extreme to fully dynamic at the other with variations and compromises in between.

A static group database can be established at initialization time and shared by all federates. The group for each update region is determined by looking up an appropriate group, given a list of federates. It is not possible to predefine every possible group for federations composed of more than a small number of workstations. However, tools such as SAT/IAT [15] or Sim^2 Toolset [16] can be used to determine a good set of groups based on expected traffic flows for a particular scenario. At run time, group selection becomes an optimization problem of selecting a group that contains all necessary federates and as few unnecessary federates as possible. In the worst case, a group consisting of all federates is used. This approach is simple and relatively robust but will certainly be less than optimal.

At the other extreme, completely dynamic grouping can be employed. A dynamic scheme creates a new group consisting of precisely the required set of federates. The new group is added to a shared group mapping database. If the necessary group already exists in the shared group mapping database it is not created. This approach can provide near optimal connectivity but may be impractical to implement in a large distributed system unless sophisticated heuristics are employed.

An intermediate approach is to permit the connectivity represented in the shared group mapping database to evolve slowly to match the requirements of each exercise. Such an approach can come close to providing the ideal connectivity while remaining practical.

Initial simulation results for such approaches used a cellified clustering technique instead of multidimensional binary trees and were presented in [17]. Current results for such approaches are shown in Figures 5 and 6. Figure 6 shows the performance of receiver-based filtering for a number of different tree depths relative to ideal filtering. As expected, the effectiveness of the algorithm increases (less traffic is delivered) as the partition size gets smaller (tree depth gets larger). This occurs because less irrelevant traffic is being forwarded to each group as the partition size is reduced. This simulation was done with rectangular extents in a two dimensional routing space. If regions are specified using shapes that more closely match the geometry of simulated objects' interest (e.g., circles), the effectiveness can be made very close to the ideal by increasing tree depth. This is possible without the explosion in multicast groups that would be experienced with a grid-based approach. Figure 5 shows performance of the receiver based prototype with other approaches.

5.3 Sender-Based Filtering

Group selection can be dynamic or static and is done by the senders' agents. The simplest approach is to statically allocate a set of groups to each subscription agent. The agent clusters update regions and assigns groups to each cluster. Federates send their data to the group for each cluster. Receivers join groups for update region clusters that match their own subscription regions.

Figure 5 shows simulation results for the sender-based filtering approach. This simulation employed a single cluster and group per federate. As the graph shows, this simple approach yields a considerable benefit over broadcast but is not nearly as efficient as grid or receiver-based approaches. However, only a very small number of groups (one per federate, i.e., 62) were required to achieve this result. Enhancements to this simple algorithm should result in considerably better performance.

6.0 CONCLUSIONS

The RTI can concurrently support a number of filtering/routing schemes so as to satisfy the differing requirements of various federations and types of data. The new techniques being prototyped and evaluated ­ receiver-based and sender-based filtering ­ appear to be very promising and are able to address many of the shortcomings of more familiar grid-based schemes.

7.0 REFERENCES