Multi-level reconfigurable self-organization in overlay services

Abstract

The design and management of networked systems that are large-scale and decentralized is challenging. These systems are usually organized in virtual networks: the overlay networks. An overlay network lies at the application-level and on top of physical or other overlay networks. Overlay networks implement complex application and organizational functionality not supported by underlying network services. This integration and design approach results in low abstraction, modularity and reconfigurability of applications that are based on overlay networks. In contrast to this practice, this thesis introduces the conceptual architecture of ASMA, the Adaptive Self-organization in a Multi-level Architecture. ASMA is the main contribution of this thesis and is designed for building middleware systems of overlay networks that provide generic capabilities to different distributed applications: the overlay services. The abstraction, modularity and reconfigurability of ASMA is achieved by its multilevel design approach. Three conceptually defined levels of overlay networks and their interactions provide discovery, structuring and coordination of system entities without a centralized management authority. The interactions between the three levels of ASMA form feedback loops that improve the quality of an overlay service incrementally. This thesis shows that a few lines of algorithmic expressions defined by ASMA are adequate to realize the complex system functionality of two introduced overlay services: (i) AETOS, the Adaptive Epidemic Tree Overlay Service and (ii) DIAS, the Dynamic Intelligent Aggregation Service. Both overlay services advance the state of the art by providing two generic application capabilities. AETOS builds and maintains overlay networks organized in tree topologies that meet different application criteria. DIAS computes different aggregation functions over a set of dynamically changing values distributed in an overlay network. Both overlay services of ASMA provide a proof-of-concept about their higher abstraction, modularity and reconfigurability at the cost of higher communication overhead compared to related work. AETOS provides self-organization of tree topologies with the graph properties of degree- bounding, ordering, balancing and completeness. AETOS performs a gossip-based discovery of nodes in a network. These nodes, ranked according to application criteria, are clustered based on their proximity computed by their ranking distance. Clustering of nodes as candidate parents and children provides a more cost-effective search space compared to random searching. Bidirectional links are negotiated and established with these parents and children based on ‘request’, ‘acknowledgment’, ‘rejection’ and ‘removal’ interactions. Different tree topologies can be self-organized by adopting adaptation strategies that hide complex clustering and selection configurations. Experimental evaluation illustrates the performance trade-offs and reconfigurability of AETOS in various experimental settings. This evaluation concludes that AETOS is a generic and flexible overlay service for the self-organization of tree topologies. DIAS makes aggregates, such as average, summation, maximum, etc., locally available in every node of an overlay network. In contrast to other related methodologies, aggregation in DIAS is function-independent, routing-independent and dynamic as aggregates are adapted if distributed input values change during runtime. DIAS achieves this abstraction and flexibility by introducing the concept of aggregation memberships. An aggregation membership provides historic information about a computed aggregation value by indicating if this value is new, outdated or duplicate. This distinction guarantees accurate computation of aggregates. It also provides two adaptation strategies based on which new or outdated aggregation values may be preferred in computations of aggregates. An explicit storage of aggregation memberships is not a scalable and decentralized aggregation approach. Nevertheless, DIAS stores aggregation memberships in probabilistic data structures: the bloom filters. A bloom filter provides large space savings at the cost of false positives. A distributed consistency mechanism is introduced to detect false positives and, therefore, prevent inaccuracies in the computations of aggregates. Experimental evaluation confirms the high accuracy of DIAS under different experimental settings and performance trade-offs. The applicability of AETOS and DIAS is studied in the domain of the Smart Power Grid. More specifically, two decentralized demand-side energy management mechanisms are introduced based on these overlay services: (i) EPOS, the Energy Plan Overlay Selfstabilization and (ii) ALMA, the Adaptive Load Adjustment by Aggregation. EPOS and ALMA are the contributions of this thesis in the application domain of the Smart Power Grid. EPOS coordinates the energy consumption of a large number of thermostatically controlled devices such as water heaters, refrigerators etc., to achieve the global system objectives. More specifically, EPOS performs self-stabilization by eliminating the oscillations and power peaks in the total energy consumption if and when it is required. Thermostatic devices are controlled by communicating software agents that generate, select and execute operational plans for their devices without direct involvement and impact on consumers. EPOS achieves energy self-stabilization by using AETOS to selforganize agents in a tree overlay network within which they perform a decentralized aggregation and coordinated decision-making of their local energy consumption. Experimental evaluation using synthetic data shows the high energy stabilization achieved in various experimental settings. ALMA complements EPOS under extreme conditions in which the Smart Power Grid requires an actual decrease or increase in the power demand due to failures or excessive micro-generation. ALMA achieves adjustments of aggregate energy consumption with possible demand options of local energy consumption, representing a wide range of comfort and economy levels, that can be pre-defined and dynamically selected by incentivized consumers. Aggregate information about power demand can be made locally available to consumers by the DIAS overlay service. The feasibility of ALMA is evaluated analytically using data from an operational Smart Power Grid: the Olympic Peninsula Smart Grid Demonstration Project. In conclusion, this thesis indicates that introducing decentralized computing systems in an information era expanding to new critical application domains, such as the Smart Power Grid, is a promising endeavor towards more sustainable development and a resource-based economy in future societies.