Analysis of Discrete Load Balancing on Heterogeneous Networks (ADLON)

• Applicant: Professor Tobias Friedrich, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 223438688

Wir befinden uns am Ende einer Ära immer steigender Prozessorleistungen. Damit müssen Computernetzwerke ihre Lasten auf eine immer größere Anzahl von Knoten balancieren. Trotz einer großen Zahl an theoretischen Studien über Lastbalancierung werden die meisten Resultate der komplexen und heterogenen Struktur dieser Netzwerke und Lastbalancierungsaufgaben nicht gerecht. Ein Großteil der Forschung beschränkt sich bisher auf die Analyse sehr wohl-strukturierter homogener Netzwerke wie vollständige Graphen, Hyperwürfel und Tori. Auf der anderen Seite verfügen viele Rechnernetzwerke heutzutage über eine inhomogene skaleninvariante Struktur, d.h., sie haben eine sehr ungleichmäßige heterogene Gradverteilung. Neben der Netzwerkstruktur, kann sich die Heterogenität auch niederschlagen in verschiedenen Jobgrößen, Rechen- und Kommunikationsgeschwindigkeiten, aber ebenso in dynamischen Veränderungen des Netzwerkes und der Lastverteilung. Mit diesem Projekt soll die Lücke geschlossen werden zwischen den vielfach untersuchten homogenen Lastbalancierungsproblemen und den theoretisch weitaus weniger verstandenen heterogenen Szenarien, die in der Praxis auftauchen. Wir werden verschiedene Protokolle untersuchen und den Einfluss von unterschiedlichen heterogenen Netzwerken und verschiedenen Lastverteilungen analysieren. Als Qualitätskriterien werden wir uns auf die Laufzeit und die Balanciertheit der Lastverteilung konzentrieren. Wir werden aber auch Aspekte der Kommunikation betrachten, wie z.B. Synchronisierung der Knoten und der verursachte Datenverkehr.

• DFG Programme: Research Grants