SFB 376 - Teilprojekt A2 Forschungsschwerpunkt: Graphzerlegungen

In der vergangen Antragsphase wurde eine hierarchische Graphzerlegung entwickelt, die für das Virtual Circuit Routing Problem einen Algorithmus mit gutem Competitive-Ratio liefert, der oblivious arbeitet, d.h., die Routingentscheidungen die der Algorithmus trifft sind unabhängig von der aktuellen Netzwerklast. In der kommenden Antragsphase möchten wir die folgenden Probleme behandeln, die sich in diesem Zusammenhang ergeben haben.

• Es ist gezeigt worden, dass für jedes beliebige Netzwerk G eine hierarchische Graphzerlegung existiert, so dass der Routing-Algorithmus ein Competitive-Ratio von O(η · n · log n) besitzt, wobei der η Faktor zwischen einem approximativen sparsest cut und dem Durchsatz eines entsprechenden Multicommodity flows für das Netzwerk G ist (d.h., für beliebige Netzwerke η = O(log n) und für z.B. planare Netzwerke η = O(1)). Diese Zerlegung kann in Polynomzeit konstruiert werden.

  Hierbei stellt sich die Frage nach einer unteren Schranke für den Competitive ratio eines Routing-Algorithmus, der oblivious arbeitet. In diesem Teilprojekt wurde eine Schranke von Ω(log n) für Gitternetzwerke gezeigt. Falls Netzwerke existieren, für die die untere Schranke superlogarithmisch ist müßte für diese Netwzerke η = ω(1) gelten. Beispiele für solche Netzwerke sind Expander für die sogar η = Θ(log n) gilt. Expander sind allerdings sehr gute Routingnetzwerke und es ist deshalb sehr einfach einen oblivious-Routingalgorithmus anzugeben, der ein Competitive-Ratio von O(log n) besitzt.

  Wir vermuten, dass es für jedes Netzwerk einen Routing-Algorithmus mit einem Competitive-Ratio nahe an log n gibt, der oblivious arbeitet. Allerdings erfordert ein Beweis dieser Vermutung Techniken, die sich grundlegend von den bisher benutzten unterscheiden. In diesem Zusammenhang stellt sich auch die Frage nach einem Algorithmus, der die bestmögliche hierarchische Zerlegung berechnet bzw. approximiert, die für ein gegebenes Netzwerk möglich ist.

• Eine weitere wichtige Fragestellung im Zusammenhang mit Routingalgorithmen ist die Frage des Platzbedarfs der für Routingtabellen benötigt wird. Das bisherige Verfahren benötigt einen Speicherplatz von O(d · n · log n) in jedem Knoten mit Grad d. Wir möchten versuchen dieses zu verbessern. Hierbei scheint der Grad des Zerlegungsbaums von besonderer Bedeutung zu sein. Deshalb möchten wir versuchen Netzwerkklassen zu identifizieren, für die ein Zerlegungsbaum mit kleinem Grad gefunden werden kann.

• Unser Routingalgorithmus verwendet als Kostenmaß die Congestion, d.h., max{L(e)}, wobei L(e) die relative Last der Kante e beschreibt, d.h., das Datenvolumen das über e geschickt wird geteilt durch die Bandbreite von e. Ein anderes viel verwendetes Kostenmaß ist die Gesamtlast, d.h. ∑ L(e). Wir möchten in der kommenden Antragsphase Kostenmaße untersuchen, die zwischen diesen beiden Extremfällen liegen. Sei L_p := (∑ L(e)^p})^1/p, die L_p-Norm. Dann beschreibt die L_0-Norm das Kostenmaß Gesamtlast und die L_∞-Norm das Kostenmaß Congestion. Für beide Normen existiert ein Routingalgorithmus der ein gutes Competitive-Ratio erreicht und oblivious arbeitet. Für die L_2-Norm ist dies nicht klar.

  Wir möchten in der kommenden Antragsphase untersuchen ob man für beliebiges p einen Routingalgorithmus entwickeln kann, der fast oblivious ist. Das heißt das Routingentscheidungen nur geringfügig von der Lastsituation abhängen sollten, z.B. nur von der Gesamtzahl der verschickten Nachrichten. Dieses könnte dazu genutzt werden effiziente Routingalgorithmen zu entwickeln, die nur ein geringes Maß an Adaptivität besitzen.

Navigationshilfe: