B02: Planning and Coordination

Multi-Mechanism-Adaption of distributed systems with discrete optimization

The central theme of the collaborative research center MAKI as a whole are runtime adaptations of mechanisms for the Future Internet, in particular by means of transitions between multiple (exchangeable) mechanisms. Thereby, mechanisms denote communication protocols or sub-functions thereof, or application level functionality such as peer-to-peer overlays, event routing mechanisms (and sub-functions thereof), etc. Coordination of cross-“layer” transitions and of transitions in entire (logical or physical) networks represent particular challenges. Sub-project B02 focuses on this transition coordination aspect; it covers both the decision about transitions (basically an optimization problem) and the coordination proper of these transitions – as to the latter, we put our focus in phase I on transitions in higher layers, i.e., in distributed systems (overlays, application level routing or multicast, etc.). This leads to different challenges in two research fields: discrete optimization and distributed systems.

Discrete Optimization: Obviously, cross-layer coordinated transitions assume multiple ‘transition-prone’ mechanisms to exist on each layer (the term layer being used in its widest sense, i.e., as an aggregate of functionally similar, i.e., ‘transitionable’ mechanisms). To determine the best overall system configuration under multiple possible transitions, both the transition costs and the expected gains of new configurations must be taken into account. To calculate both, we will develop discrete optimization algorithms for induced network structures. Here, Prof. Weihe and his group will contribute their extensive expertise in discrete optimization. The overall challenge is addressed in two steps: During the first two years, we will implement algorithms under the assumption that all nodes in the network use the same configuration. Furthermore, we will use a central component for ‘computing’ and taking decisions and for coordinating them (including transitions on different layers). Afterwards, we will apply that knowledge to distributed systems with different local configurations. Eventually, B02 aims at distributing both the planning component (based on discrete optimization) and the coordination component. Tradeoffs between partial distribution (with components controlling a sub-network each) and fully distributed solutions (based as much as possible on local and neighborhood information) will be investigated and compared to centralized solutions, thereby investigating the effect of network scale.

From the point of view of distributed systems research, the first project stage is focused on concepts and methods for developing and executing MAKI compatible systems as described, i.e., systems that follow the principles of per-layer mechanism transitions and cross-layer optimization. In this respect, the group of Prof. Mühlhäuser has carried out important preliminary work within the DFG research group QuaP2P (FOR 733). Two main challenges shall be listed here as follows. 1) Novel methods and interfaces for the interplay of the coarse-level system parts, i.e., the one that orchestrates transitions and the one that carries out optimization and takes transition decisions; further system parts may exist, in particular one for monitoring the network-wide system state as input for, e.g., the optimization. Note that all these system parts may exist at different degrees of centralization vs. decentralization, making algorithms for their interplay more challenging. 2) Novel methods and interfaces ‘inside’ the system part that orchestrates transitions: this concerns three kinds of components: those responsible for overall and for layer-specific orchestration, those carrying out transitions, and those that realize the mechanisms themselves. In another dimension, project B02 plans to provide both development support for modular, exchangeable mechanisms and run-time support, i.e., support for cross-layer, network-wide transition between configurations in a real Internet configuration.

An additional task is the design and implementation of a concrete experimental system that follows the above-described MAKI structure and principles. Our work in this field will lead to a contribution to research about Cloudlets, i.e., Cloud-like infrastructures which can (partly or entirely) “roam” with the user and which are thus almost always available in the user’s proximity with high availability, context awareness, and low delay. Four core layers are currently planned: A: Application, M: Medium, T: (Cloudlet-) Topology, and O: Overlay. Each layer is comprised of several alternative mechanisms. Two more layers are planned: a layer S (application scenario) on top that simulates the network load, and a ‘base layer’ B that provides two mobile communication protocol stacks (infrastructure and ad-hoc communication (cf., sub-project C01). Depending on the environment – as measured mainly in the upper layer and the overall network state – the optimal multi-mechanism configuration will be found (by means of discrete optimization) and executed (using the above-described methods and interfaces). Due to the complexity of implementing a running system, we envision the need to rudimentarily simulate basic functionality of other sub-projects, e.g., state transition (sub-project A03) and monitoring (sub-project B01), as opposed to fully integrating their software-under-development in the beginning. Eventually, results of these sub-projects will replace the corresponding rudimentary implementations. Core B02 components will be needed for the cross-layer (network wide) optimization, for per-layer transition, and for the overall optimization. Towards comparative performance studies in large-scale networks, the realization of a corresponding simulator is indispensable. Additionally, the development of experimental systems (experimental implementation, simulation) as described in this paragraph will be synchronized with the demonstrator implementation that is scheduled as an overall MAKI activity.

Subproject leader B02

  • Prof. Dr. rer. nat. Max Mühlhäuser
  • Prof. Dr. rer. nat. Karsten Weihe