Aufgabe:
(1) Wieso benötigt ein Oblivious Routing-Protokoll benötigt zum Routen von f mindestens max{Cf, Df} Schritte?
(2) Wieso benötigt ein Oblivious Routing-Protokoll benötigt zum Routen von f höchstens Cf * Df Schritte? (Wobei jeder Prozessor, in dem sein Puffer nicht leer ist, ein Paket weiterleitet)
Also Laufzeit T ist max{Cf, Df} <= T <= O(Cf * Df)
Zu Oblivious Routing:
Sei M = ([n], E) ein Netzwerk. Für i, k ∈ [n] sei w(i,k) ein Weg von i nach k in M. W={w(i,k) | i, k ∈ [n]} ist ein Wegesystem in M
Ein Routingprotokoll, das nur Routingwege aus W benutzt, heißt oblivious.
f: [n] × [p] → [n] ist eine Routingfunktion.
Sie beschreibt folgende Aufgabe:
-Jeder Knoten i ∈ [n] hat p Pakete,
-sein j-tes Paket muss zum Prozessor f(i,j) geroutet werden.
Ein Prozessor kann in Jedem Schritt ein Paket weiterleiten und Congestion und Dilation seien wie folgt definiert:
Knoten-Congestion von f in Knoten r:
Cf(r) = #{(i,j) ∈ [n] × [p], Knoten r liegt auf w(i, f(i,j))}
Die Congestion von f ist Cf = max {Cf(r), r ∈ [n]} (Zum Weg gehören auch Start - und Endpunkte)
Die Dilation von f ist Df, die maximale Länge der Wege aus
{w(i,f(i,j)), (i,j) ∈ [n] × [p]}
Problem/Ansatz:
(1) Verstehe ich soweit. Routet man ein Paket von i nach f(i,j), kann dies nur die Länge des Weges sein, was gleich Df ist oder wenn mehrere Pakete entsprechend über einen Knoten r gehen, dementsprechend es nur Cf sein kann, falls diese Größer ist als die Dilation, weil beispielsweise Dilation könnte 3 sein, aber wir wollen 10 Pakete über den gleichen Weg schicken; daraus folgt, dass wenn alle über den gleichen Knoten r gehen, die Laufzeit entsprechend Cf ist
(2) Verstehe ich widerum nicht. Wenn jeder Prozessor in jedem Schritt nur ein Paket versendet und sein Puffer nicht leer ist, wie kommen wir auf die Obergrenze Cf * Df
Vielleicht kann ja jemand helfen, auch wenn er sich auf dem Themengebiet nicht zwingend auskennt.
