Summary An examination of the multidimensional range query in existing peer‐to‐peer (P2P) overlay networks indicates that multidimensional range queries are sensitive to underlying topologies; this is because partitioning and mapping of multidimensional data space are two interconnected parts of a process that must be carried out cooperatively. The first section focuses on how to preserve data localities, whereas the second section concerns how to accommodate and maintain data localities at the P2P overlay layer. There are many studies that have been conducted on the first section since 1966, and those works that are well accepted are mostly based on recursive decomposition, which forms a tree structure in nature. However, less effort has been made to provide comparable support from the P2P overlay layer. In our previous work, we proposed the Hierarchically Distributed Tree (HD Tree) in order to better support multidimensional range queries in the P2P overlay network. This paper further explores error‐resilient routing and load balancing strategies that can be employed in the HD Tree. We also provide a complete set of experimental results for all routing operations: Join and Leave of nodes, range queries at different levels of selectivity, and the dynamic load balancing scheme. Comparisons are made by conducting simulations under both the ideal and the error‐prone routing environment and within various ary HD Trees. The experimental results show that load balancing in the HD Tree can be adjusted dynamically and globally, and it is actually a trade‐off between distributing the basic load and the involvement of nodes in range querying. The experimental results also indicate that a maximum of 10 percent of routing nodes’ failures do not have significant effects on the performance of range queries. However, a lower ary HD Tree appears to have better routing performance, whereas a higher ary HD Tree achieves a higher fault‐tolerant capacity. Nevertheless, the performance of range queries in a higher ary HD Tree can be further optimized if all possible routing options can be fully explored in the error‐prone routing environment. Copyright © 2013 John Wiley & Sons, Ltd.

The Hierarchically Distributed Tree (HD Tree) is a novel distributed data structure built over a complete tree. The purpose of proposing this new data structure is to better support multi-dimensional range query in the distributed environment. HD Tree doubles the number of neighbors at the cost of doubling total links of a tree. The routing operation in HD Tree is supposed to be highly error-resilient. In HD Tree, the routing table size is determined by the system parameter k, and the performance of all basic operations are bound by O(lg(n)). Multiple routing options can be found between any two nodes in the system. This paper explores fault tolerant routing strategies in HD Tree. The experimental results produce very limited and unnoticeable increases in routing cost when conducting range queries in an error-prone routing environment. The maximum failures we have tested are about 5 percent of routing nodes. The experimental results also indicate that higher fault tolerant capability requires finer consideration in the design of the error-resilient routing strategy.

The Hierarchically Distributed Tree (HD Tree) is a novel distributed data structure. The purpose of proposing this new data structure is for better maintaining data localities with exponentially expanding and extending rate, and at the same time adapting the hierarchical structure to the distributed environment. In HD Tree, the routing table size is determined by the system parameter k, the performance of all basic operations are bound by O(lg(n)). The add-on distributed structure in HD Tree generates multiple routes between any two nodes in the system, and the progressive routing in HD Tree can be conducted more strategically because of the global awareness about the location of each node. Operations in HD Tree can be designed highly error resilient, and the hierarchical nature in HD Tree makes load balancing straightforward, and it is massively scalable not only in multidimensional rang queries, but also in constructing and maintaining P2P overlay structures.

There are two basic concerns for supporting multi-dimensional range query in P2P overlay networks. The first is to preserve data locality in the process of data space partitioning, and the second is the maintenance of data locality among data items with an exponentially expanding rate and an exponentially extending rate. The first problem has been well addressed by using recursive decomposition schemes, such as Quad tree, K-d tree, Z-order, and Hilbert curve. While the second problem was recently identified by our novel data structure: HD Tree. This paper is a follow-up to our previous work in HD Tree. In this paper, we explore how data locality can be easily maintained, and how range query can be efficiently supported in HD Tree. This is done by introducing two basic routing strategies, hierarchical routing and distributed routing. Although hierarchical routing can be applied to any two nodes in the system, it generates high volume traffic towards nodes near the root, and has very limited options to cope with a node failure. On the other hand, distributed routing concerns source and destination pairs only at the same depth, but traffic load is bound to some nodes at two neighboring depths, and multiple options can be found to redirect a routing request. Because HD Tree supports multiple routes between any two nodes in the system, routing in HD Tree is very flexible, and can be designed for many purposes, like fault tolerance, or dynamic load balancing. Distributed Routing Oriented Combined Routing algorithm is one such routing strategies implemented so far. It is a hybrid algorithm combining advantages from both the hierarchical routing and the distributed routing. The experimental results show that the DROCR algorithm achieves considerable performance gain over the equivalent tree routing at the highest depth examined. In the experiment of supporting multi-dimensional range query, we employ the Z-order space filling curve over the HD Tree overlay layer. We are expecting that the performance of range query will vary proportionally with the change of range size, and reasonably with the increase of dimensionality.

Data Distribution Management (DDM) is one of the most critical component of any large-scale interactive distributed simulation systems. The aim of DDM is to reduce and control the volume of information exchanged among the simulated entities (federates) in a large-scale distributed simulation system. In order to fulfill its goal, a considerable amount of DDM messages needs to be exchanged within the simulation (federation). The question of whether each message should be sent immediately after it is generated or held until it can be grouped with other DDM messages needs to be investigated further. Our experimental results have shown that the total DDM time of a simulation varies considerably depending on which transmission strategy is used. Moreover, in the case of grouping, the DDM time depends on the size of the group. In this paper, we propose a novel DDM approach, which we refer to as Adaptive Grid-based (AGB) DDM. The AGB protocol is distinct from all existing DDM implementations, because it is able to predict the average amount of data generated in each time step of a simulation. Therefore, the AGB DDM approach controls a simulation running in the most appropriate mode to achieve a desired performance. This new DDM approach consists of two adaptive control parts: 1) the Adaptive Resource Allocation Control (ARAC) scheme and 2) the Adaptive Transmission Control (ATC) scheme. The focus of this paper is on the ATC scheme. We describe how to build a switching model to predict the average amount of DDM messages generated and how the ATC scheme uses this estimation result to optimize the overall DDM time. Our experimental results provide a clear evidence that the ATC scheme is able to achieve the best performance in DDM time when compared to all existing DDM protocols using an extensive set of experimental case studies.

Multi-casting and Data Distribution Management (DDM) play a critical role in the design of future generations of large-scale distributed simulation systems, in which a large number of DDM messages are exchanged between the participating entities. Thus, communication overhead is one of the most challenging issues that needs to be studied and it must be investigated further whether each message should be sent immediately after it is generated during the simulation or held until it can be grouped with other DDM messages. Very little work has been done to answer these questions. Our experimental results have shown that the total DDM time of a simulation varies considerably depending on which transmission strategy is used. Moreover, in the case of message grouping, the DDM time depends on the size of the group. In this paper, we propose a novel Adaptive Transmission Control (ATC) scheme for DDM. As opposed to previous DDM schemes, our proposed scheme has the ability to predict the average amount of DDM messages generated in each timestep of a simulation. Therefore, the ATC scheme is able to control a simulation running in the most appropriate mode to achieve a desired performance. In order to accomplish this goal, we will show how to use the switching model to predict the average amount of DDM messages generated in the grid-based DDM system. The experimental results are used to validate the correctness of the switching model and exhibit improved performance over previous schemes.

The goal of this paper is to provide an optimal solution for data distribution management (DDM) in large-scale distributed simulations. Until now, all existing DDM approaches have tried to make DDM more efficient in different ways; however, none has been able to optimize performance. The main reason for this inability is that these approaches manipulate the data generated in a simulation without evaluating the size of it. We propose a novel resource allocation scheme, the adaptive resource allocation control scheme (ARAC). The ARAC scheme is designed to optimize resource allocations for local and distributed processing work at each federate according to the size of the simulation. Efficiency is achieved by applying the analysis results of a static probability model, which we call the matching model. Performance comparisons between the existing grid-based approaches and the new adaptive approach show that the new scheme is much more flexible in adapting to various simulation sizes and comes much closer to an optimal solution. The novelty of the ARAC scheme is that it is able to scale the size of a simulation and control the simulation itself by running it in the most appropriate mode to achieve the desired efficiency. As a final result, the optimum performance is best approached.

Data distribution management (DDM) plays a key role in traffic volume control of large-scale distributed simulations. In recent years, several solutions have been devised to make DDM more efficient and adaptive to different traffic conditions. Examples of such systems include region-based, fixed grid-based, hybrid, and dynamic grid-based (DGB) schemes. However, less effort has been made to improve the processing performance of DDM techniques. This paper presents a novel DDM scheme called the adaptive dynamic grid-based (ADGB) scheme that optimizes DDM time through analysis of matching performance. ADGB uses an advertising scheme in which information about the target cell involved in the process of matching subscribers to publishers is known in advance. An important concept known as distribution rate (DR) is devised. DR represents the relative processing load and traffic volume generated at each federate. The matching performance and DR are used as part of the ADGB method to select, throughout the simulation, the devised advertisement scheme that achieves maximum gain with acceptable network traffic overhead. Performance estimation and analysis of ADGB have shown that given an ideal matching probability, an efficiency gain of a maximum of 66% over the DGB scheme can be achieved. The novelty of the ADGB scheme is its focus on improving performance, an important (and often forgotten) goal of DDM strategies

This paper presents a novel adaptive dynamic grid-based data distribution management (DDM) scheme, which we refer to as ADGB. The main objective of our protocol is to optimize DDM time through matching probability (MP) and federates' performance. A distribution rate (DR) along with MP are used as part of the ADGB method to select, throughout the simulation, from different devised advertisement schemes, the best scheme to achieve maximum gain with acceptable network traffic overhead. As opposed to previous protocols, the novelty of our ADGB scheme is its focus on improving overall performance, an important goal for DDM strategy. In this paper, we present our scheme and highlight its performance analysis.