Adaptive Self-Organization in Distributed Tree Topologies

Introduction

Distributed systems and their applications often require an organizational structure to perform their operations efficiently. Certain topologies of overlay networks are defined by graph properties that enable or enhance the performance of a specific application. Tree topologies are one of them. Their properties, e.g., path uniqueness, and the hierarchy they reflect enable operations such as decentralized search, decision-making, aggregation or information dissemination. These operations are fundamental in various application domains such as distributed databases (González-Beltrán et al., 2008; Zhuge & Feng, 2008), application-level multimedia multicasting (Tan et al., 2005a) and grid computing (Chakravarti et al., 2006).

However, trees suffer from lack of redundancy and therefore their structure is very sensitive to single node or link failures. Moreover, a tree experiences heterogeneous load, meaning that the nodes close to the root of the topology receive messages forwarded from all the other nodes at the bottom part of this tree. This effect is also related to the impact of a failure that is much higher for nodes close to the root of a tree. All of these issues make the use of trees in dynamic distributed environments challenging and sometimes infeasible.

Self-organization in trees is required to overcome these limitations. A robust tree requires both building and maintenance during runtime of a distributed application. Nodes self-organize themselves in a tree topology that ideally minimizes the impact of their failures. One way to achieve this optimization is by ordering a tree according to specific application criteria, i.e., the performance profile of nodes. An optimized tree may also have constraints such as the number of children with which each node can connect. All of these criteria should be met during self-organization.

This paper studies the adaptation strategies of AETOS, the Adaptive Epidemic Tree Overlay Service (Pournaras et al. 2010b,a). Self-organized tree topologies with different graph properties are formed by simply using certain adaptation strategies. This paper shows how these strategies can be combined dynamically, providing a powerful meta-level of adaptation and abstraction in the self-organization of tree topologies based on which a wide range of performance trade-offs can be explored as confirmed by the experimental findings of this paper.

Some of the basic system components of AETOS are described in our earlier work (Pournaras et al., 2010b,a). In contrast, the contribution of this paper is threefold (Pournaras, 2013):

• 1.

  The problem of building and maintaining robust tree topologies is illustrated as a general graph theoretic problem. The selection of graph properties studied in this paper is grounded to applications that perform distributed operations based on tree topologies.

• 2.

  The design of adaptation strategies is improved to achieve higher performance and abstraction as shown in new extensive experimental results studied in this paper. Moreover, this paper extends the adoption of adaptation strategies from static to dynamic resulting in improved performance.

• 3.

  A survey of related methodologies is illustrated that distinguishes the more generic features of AETOS compared to other application-dependent mechanisms for building and maintaining tree topologies.

The organization of this paper is outlined as follows: ‘Problem Description’ illustrates graph properties of tree topologies and their relation with distributed applications. It also defines performance metrics for self-organization. ‘System Overview’ provides a high-level overview of AETOS.

‘Dissemination and Collection’ illustrates the bottom level of the AETOS architecture. ‘Clustering’ discusses the input and adaptations of the middle level. ‘Building and Maintenance’ shows the establishment of parent-child links in the top level. Moreover, ‘Adaptation Strategies’ illustrates a number of generic strategies engaged in the middle level of AETOS. ‘Experimental Evaluation’ follows. ‘Comparison with Related Work’ compares AETOS with related methodologies. ‘Conclusions’ concludes this paper.