A1: Modeling

Graph-based Topology Models for Self-Organizing Network Structures

Subproject A1 investigates the development methods for Topology Control mechanisms. The basic idea is to use graph transformations for specification and local algorithms for the realization of Topology Control mechanisms. In phase I, a development methodology for reactive Topology Control mechanisms was developed. In phase II, A1 aims at developing federations of Topology Control (multi-)mechanisms (in contrast to isolated Topology Control mechanisms in phase I). These Topology Control (multi-)mechanisms cooperate across network layers and (geographic or logic) regions. The duration and probability distribution of transitions will be taken into account. The development methodology is also extended to support proactive TC transitions.

Subproject A1 tackles the systematic development of novel approaches to adapt complex network topologies in a distributed and self-organized way. This task is subdivided into constructing individual Topology Control mechanisms and developing approaches for coordinating multiple Topology Control mechanisms, e.g., by multi-mechanism transitions. A Topology Control multi-mechanism controls how a communication system switches from one Topology Control mechanism to another on one particular network layer and in one particular (geographic or logic) region. Based upon the set of available Topology Control multi-mechanisms, we develop a federated approach that enables the coexistence of loosely coupled Topology Control mechanisms and transitions across borders of network layers and regions.

We apply graph transformation for the rule-based specification, and local algorithms for the distributed and efficient implementation of Topology Control mechanisms. Our step-by-step approach is structured as follows: First, we represent topologies as attributed graphs, enriched with additional integrity constraints. Then, we translate the considered optimization goals into graph patterns (e.g., using so-called motifs). We distinguish between positive patterns whose presence in the topology influences the system performance positively, and negative patterns whose presence indicates performance problems. This pattern-based specification is then used to derive the to-be-constructed Topology Control mechanism as follows: i) We synthesize a graph transformation algorithm that restores violated integrity constraints and optimization goals in a semi-automatic way. ii) We evaluate this algorithm in a simulation environment that allows us to assess self-adaptive network topologies. iii) We transform promising graph transformation algorithms into local algorithms, which operate in a distributed way and respect the limited resources of hardware devices. iv) We evaluate each local algorithm in a testbed environment.

In phase I of MAKI, we focused on the following five aspects:

• Developing a systematic construction methodology for Topology Control mechanisms (supported by a Wireless Sensor Network case study).

• Developing an approach based on graph transformation for synthesizing Topology Control algorithms that are efficient and correct-by-construction. Topology Control algorithms developed in this way are able to fix any possible violation of the integrity constraints using a minimal number of topology modification operations. For this purpose, we extended established approaches from the graph transformation domain by introducing a domain-specific notion of soft constraints that may be violated temporarily and supporting complex attribute constraints (described as constraint satisfaction problems).

• Developing a simulation environment based on the network simulator Simonstrator and the graph transformation tool eMoflon. We extended the graph pattern matching engine of eMoflon to identify (positive and negative) patterns incrementally.

• Developing a generic local algorithm for the motif-based optimization of topologies. This algorithm takes a target distribution of motifs (also called target signature) as input and iteratively adapts the topology to approach the target distribution.

• Carrying out case studies in the following domains: Wireless Sensor Networks (to test the applicability of the development methodology described above), search overlays (transitions between BubbleStorm and Gnutella), network coding, video streaming, and monitoring. Most of the case studies have been conducted in cooperation with other sub-projects and the project group Demonstrator.

In phase II of MAKI, we will extend our development methodology as follows:

Automatization: We will investigate how to automatize (the currently manual) step from abstract graph transformation algorithms (for simulation purposes) to the corresponding local algorithms (for testbed evaluation purposes). From a conceptual point of view, we will need to decompose complex graph transformation rules into rules that can be executed based on the available local knowledge in a semantics-preserving manner. From a technical point of view, we plan to adapt the modular code generation backend of eMoflon.

Generalization: Besides continuing our work in the Wireless Sensor Networks domain, we will address new application domains such as Software-Defined Networks, In-Network Processing and Complex Event Processing.

Coexistence: In phase I, we mainly considered isolated Topology Control mechanisms, which operate within one network layer and region. In phase II, we widen our view to federations of Topology Control mechanisms, which operate across the borders of network layers and regions and support transitions between different Topology Control mechanisms (either discretely or in a fading manner).

Proactivity: Simulating realistic environment models and modeling non-deterministic Topology Control mechanisms will require us to extend our models and the simulation environment with support for timed and probabilistic graph transformation. We will investigate how probabilistic and stochastic graph transformation can be used to analyze crucial properties of Topology Control (multi-)mechanisms such as stability. The analysis results can then be used to plan proactive Topology Control transitions.

In summary, our key objective for phase II is to develop a methodology for constructing correct and efficient federations of (reactive and proactive) Topology Control mechanisms that are coordinated across network layers and regions by multi-mechanism transitions.

Subproject leader A1

  • Prof. Dr. rer. nat. Max Mühlhäuser
  • Prof. Dr. rer. nat. Andy Schürr