Analyse und Referenzen für Koch-Schneeflocken-ähnliche (und andere exotische) Netzwerktopologien

10

Bei Computernetzwerken und beim Entwurf von Hochleistungsclustercomputern bezieht sich die Netzwerktopologie auf den Entwurf der Art und Weise, wie Knoten durch Verbindungen verbunden werden, um ein Kommunikationsnetzwerk zu bilden. Zu den gängigen Netzwerktopologien gehören Netz, Torus, Ring, Stern, Baum usw. Diese Topologien können analytisch untersucht werden, um Eigenschaften in Bezug auf ihre erwartete Leistung zu bestimmen. Zu diesen Merkmalen gehören der Durchmesser (maximaler Abstand zwischen einem Knotenpaar in Bezug auf die Anzahl der Verbindungen, die gekreuzt werden müssen, wenn solche Knoten kommunizieren), der durchschnittliche Abstand zwischen Knoten (über alle Knotenpaare im Netzwerk) und die Halbierungsbandbreite (die Worst-Case-Bandbreite zwischen zwei Hälften des Netzwerks). Natürlich gibt es auch andere Topologien und Metriken.

Stellen Sie sich eine Netzwerktopologie vor, die auf der Koch-Schneeflocke basiert. Die einfachste Inkarnation einer solchen Topologie besteht aus drei Knoten und drei Verbindungen in einem vollständig verbundenen Aufbau. Der Durchmesser beträgt 1, die durchschnittliche Entfernung 1 (oder 2/3, wenn Sie Kommunikationen innerhalb eines Knotens einschließen) usw.

Die nächste Inkarnation der Topologie besteht aus 12 Knoten und 15 Verbindungen. Es gibt drei Cluster mit drei Knoten, wobei jeder Cluster durch drei Verbindungen vollständig verbunden ist. Zusätzlich gibt es die drei ursprünglichen Knoten, die die drei Cluster über sechs zusätzliche Links verbinden.

Tatsächlich wird die Anzahl der Knoten und Verbindungen in der Inkarnation durch die folgenden Wiederholungsrelationen beschrieben: N ( 1 ) = 3 L ( 1 ) = 3 N ( k + 1 ) = N ( k ) + 3 L ( k ) L. ( k + 1 ) = 5 L ( k ) Hoffentlich ist die Form dieser Topologie klar; Inkarnation k sieht aus wie die kk

N(1)=3
L(1)=3
N.(k+1)=N.(k)+3L.(k)
L.(k+1)=5L.(k)
k Inkarnation der Schneeflocke Koch. (Ein wesentlicher Unterschied besteht darin, dass ich für das, was ich vorhabe, bei aufeinanderfolgenden Iterationen tatsächlich die Verbindung zwischen den 1/3 und 2/3 Knoten beibehalte, so dass jedes "Dreieck" vollständig verbunden ist und die obigen Wiederholungsrelationen gelten).kth

Nun zur Frage:

Wurde diese Netzwerktopologie untersucht und wenn ja, wie heißt sie? Gibt es Referenzen, wenn es ausgiebig untersucht wurde? Wenn nicht, wie groß sind Durchmesser, durchschnittliche Entfernung und Halbierungsbandbreite dieser Topologie? Wie vergleichen sich diese in Bezug auf Kosten (Links) und Nutzen mit anderen Arten von Topologien?

Ich habe von einer "Stern der Sterne" -Topologie gehört, die meiner Meinung nach ähnlich, aber nicht identisch ist. Wenn überhaupt, scheint dies eher ein "Ring der Ringe" oder etwas in dieser Richtung zu sein. Natürlich könnten Änderungen an der Definition dieser Topologie vorgenommen und erweiterte Fragen gestellt werden (z. B. könnten wir Links, die in früheren Phasen eingeführt wurden, unterschiedliche Bandbreiten zuweisen oder die Planung oder Datenplatzierung für eine solche Topologie erörtern). Generell interessiere ich mich auch für gute Referenzen für exotische oder wenig untersuchte Netzwerktopologien (unabhängig von der Praktikabilität).

Nochmals, entschuldigen Sie sich, wenn dies Unkenntnis der relevanten Forschungsergebnisse zeigt und alle Erkenntnisse geschätzt werden.

Patrick87
quelle

Antworten:

3

Keine klare Antwort, aber ich kann noch keine Kommentare abgeben. Ich denke, Sie verwechseln die Koch-Schneeflocke mit der Sierpinski-Dichtung / dem Dreieck. Eine Koch-Topologie wäre nur gleichbedeutend mit einem Pfad. Das Sierpinski-Dreieck hat die von Ihnen beschriebenen Eigenschaften.

Ein kurzer Blick auf Google zeigt eine Fülle von Artikeln und Webseiten in Sierpinski-Netzwerken, obwohl wenig Übereinstimmung über die genaue Topologie besteht.

Peter
quelle