A1 befasst sich mit der systematischen Entwicklung neuartiger Verfahren für die verteilte und selbstorganisierende Adaption komplexer Netzwerktopologien. Dies umfasst sowohl die Konstruktion einzelner Topologiekontroll- Mechanismen (TC-Mechanismen) als auch den Entwurf von Verfahren zur Koordination verschiedener TC-Mechanismen bspw. durch Multi-Mechanismen-Transitionen. Eine TC-Multi-Mechanismen-Transition kontrolliert das Umschalten zwischen verschiedenen TC-Mechanismen in einer Netzwerkregion auf einer Kommunikationsschicht. Darauf aufbauend berücksichtigt ein föderierter Ansatz die Koexistenz verschiedener lose gekoppelter TC-Mechanismen und -Transitionen über Netzwerkschichten- und Regionengrenzen hinweg.
Für die Entwicklung von TC-Mechanismen werden Graphtransformationen (GTs) zur regelbasierten Spezifikation und lokale Algorithmen zur verteilten effizienten Implementierung der betrachteten Verfahren wie folgt verwendet: Zunächst werden Topologien als attributierte Graphen mit zusätzlichen Integritätsbedingungen modelliert; relevante Optimierungsziele werden zu strukturellen Eigenschaften der eingeführten Graphklasse in Beziehung gebracht und ebenfalls in Integritätsbedingungen übersetzt. Dabei kommen Graphmuster (z. B. in Form sogenannter Motifs) zum Einsatz, deren Existenz in einer Topologie sich als positiv oder negativ für die betrachteten Optimierungsziele einstufen lässt. Davon ausgehend werden die gewünschten TC-Mechanismen wie folgt abgeleitet: i) Es wird ein Graphtransformations-Algorithmus (teil-)automatisch synthetisiert, der verletzte Integritätsbedingungen (Optimierungsziele) einer Topologie wiederherstellt. ii) Dieser Algorithmus wird in einer Umgebung evaluiert, welche die Simulation einer Kommunikationsanwendung auf einer selbstadaptiven Netzwerktopologie erlaubt. iii) Anschließend werden erfolgreich evaluierte Graphtransformations-Algorithmen in verteilte lokale Algorithmen auf ressourcenbeschränkte Kommunikationsknoten eines Testbeds übersetzt und iv) in diesem Testbed erneut evaluiert.
Der Fokus von A1 in Phase I von MAKI lag auf den folgenden fünf Punkten:
- Entwicklung der systematischen Konstruktionsmethodik für TC-Mechanismen am Beispiel drahtloser Sensornetzwerke.
- Entwicklung von Syntheseverfahren für Graphtransformations -basierte TC-Algorithmen, die effizient und per Konstruktion korrekt arbeiten. Beliebige Verletzungen von Integritätsbedingungen werden hierbei mit den dafür minimal notwendigen Topologieanpassungen eliminiert. Hierfür wurden bekannte Graphtransformations-Verfahren so erweitert, dass sie nicht nur einfache strukturelle, sondern auch (möglicherweise) zeitweise verletzte, komplexe und auf Knoten-/Kantenattributen basierende Integritätsbedingungen behandeln können.
- Entwicklung einer Simulationsumgebung, die den Netzwerksimulator Simonstrator mit dem Graphtransformations-Werkzeug eMoflon integriert. Letzteres wurde dafür um neue Konzepte zur inkrementellen Identifikation von (unerwünschten) Graphmustern erweitert.
- Entwicklung eines lokalen Algorithmus zur generischen Motif-basierten Optimierung von Topologien, welcher eine Motif-Häufigkeitsverteilung als Eingabe erhält und eine Topologie derart modifiziert, dass sich die Häufigkeitsverteilung der Motifs schrittweise an die vorgegebene Verteilung annähert.
- Durchführung einer Fallstudie aus dem Bereich drahtloser Sensornetzwerke zur Evaluation der oben genannten Konstruktionsmethodik für TC-Mechanismen sowie Untersuchung von Such-Overlay-, Network-Coding-, Video-Streaming- und Monitoring-Topologien in Zusammenarbeit mit anderen Teilprojekten und der Projektgruppe Demonstrator.
In Phase II von MAKI wird die Konstruktionsmethodik wie folgt substantiell weiterentwickelt:
Automatisierung: Der bislang rein manuell durchzuführende Übergang von abstrakten Graphtransformations-Algorithmen (zu Simulationszwecken) zu konkreten lokalen Algorithmen (zur Evaluation im Testbed) wird durch den Einsatz anpassbarer Codegeneratoren sowie durch die semantikerhaltende Zerlegung von komplexen GT-Regeln in rein lokal ausführbare einfachere Regeln teilautomatisiert.
Generalisierung: Zusätzlich zu der bislang untersuchten Anwendungsdomäne drahtloser Sensornetzwerke werden in Kooperation mit anderen Teilprojekten auch Adaptionsverfahren für Software-definierte Netzwerke, In-Network-Processing und Complex Event Processing studiert.
Koexistenz: Anstelle der Betrachtung eines einzelnen TC-Mechanismus in einer Schicht eines Kommunikationssystems werden Föderationen solcher Mechanismen betrachtet, die über Schichten und logische oder geographische Netzwerkregionen hinweg miteinander kooperieren und die Transition zwischen verschiedenen TC-Mechanismen (mit diskreter oder kontinuierlicher Umschaltung) unterstützen.
Proaktivität: Zur Definition realistischerer Umgebungsmodelle für Simulationen und die Modellierung nichtdeterministischer TC-Verfahren werden zeit- und wahrscheinlichkeitsbehaftete Graphtransformation betrachtet und in die Simulationsumgebung integriert. Zudem wird untersucht, ob wahrscheinlichkeitsbehaftete Graphtransformationen eine geeignete Basis für die analytische Betrachtung weiterer Eigenschaften von TC-Verfahren wie Stabilität und den Übergang von reaktiven zu proaktiven TC-Verfahren bieten.
Zusammenfassend verfolgt A1 in Phase II von MAKI das Ziel, eine Methodik für die Konstruktion korrekter und effizient implementierter Föderationen reaktiver und proaktiver TC-Verfahren zu entwickeln, die sich schichten- und regionenübergreifend koordinieren und Multi-Mechanismen-Transitionen zwischen verschiedenen Topologiearten und -kontrollstrategien unterstützen.
