linux-l: Heute im Tagesspiegel ...

Martin v. Loewis loewis at informatik.hu-berlin.de
Mi Jul 9 10:30:01 CEST 1997


> Sorry, ich hab' gerade ein Brett vor'm Kopf. Wer fordert denn, dass die
> Verbindungen paarweise senkrecht sein sollen und warum?

Nun, bei einem mathematischen Würfel sind zwei beliebige Kanten
entweder parallel oder senkrecht zueinander (wobei das Quadrat der
zweidimensionale Würfel ist).
Eine weitere, topologisch interessante Eigenschaft des Würfels ist:
Im n-dimensionalen Würfel sind zwei beliebige Eckpunkte höchstens n
Kanten voneinander entfernt (maW, der Durchmesser ist n).
Das ist für ein Rechnernetz wichtig, da es über die maximale Zeit
entscheidet, die ein Paket braucht.

> 		 | 	 | 	 | 	 |
> 	       -[X]-----[X]-----[X]-----[X]-
> 		 | 	 | 	 | 	 |
> 	       -[X]-----[X]-----[X]-----[X]-
> 		 | 	 | 	 | 	 |
> 	       -[X]-----[X]-----[X]-----[X]-
> 		 | 	 | 	 | 	 |
> 	       -[X]-----[X]-----[X]-----[X]-
> 		 | 	 | 	 | 	 |
> 
> In diesem zweidimensionalen Netz ist jeder Knoten mit seinen vier
> Nachbarn verbunden. Jeder Knoten, bis auf die am Rand.

Diese Vernetzung ist ja auch kein Würfel. Wenn die Knoten am Rand
keine Verbindungen nach außen haben (maW weniger als vier
Verbindungen), ist es ein Gitter (mesh). Der Durchmesser der
4x4-Gitters ist 8 - die beiden Eckpunkte sind am weitesten voneinander
entfernt.
Wenn Du die oberen und unteren sowie die linken und rechten Knoten
miteinander verbindest, erhälst Du einen Torus. Der hat einen
kleineren Durchmesser als das Gitter, ist allerdings nicht mehr
zweidimensional - Du kannst ihn nicht kreuzungsfrei in die Ebene
einbetten.

Andere Kriterien, um eine Vernetzung zu bewerten, sind:
- wieviele Verbindungen werden insgesamt benötigt?
  (Länge der Gesamtverdrahtung)
- wenn ich zwei beliebige Knoten auswähle, wie groß ist ihr Abstand?
  (mittlerer Abstand)
- wenn ich zwei beliebige Knoten und eine beliebige Kante auswähle,
  wie groß ist die Wahrscheinlichkeit, daß ein Paket zwischen den
  Knoten über die Kante geht?
  (Bandbreitenbedarf einzelner Kanten)
- wieviele alternative Wege gibt es zwischen zwei Knoten? Wenn ich
  eine Kante weglasse, wieviele gibt es dann?
  (Fehlertoleranz)
Nach diesen Kriterien kommt der Hyperwürfel oft am besten weg,
deshalb werden große Rechnernetze oft nach dieser Topologie verschaltet.

> In einem vierdimensionalen Raum wuerde ich erwarten, dass jeder Knoten
> acht Nachbarn hat (rechtwinkelige Anordnung vorrausgesetzt).

In einem Gitter, ja. Bei einem Würfel sind jedoch nur Koordinatenwerte
0 und 1 erlaubt, so daß an jeder Ecke in jeder Dimension nur eine
Kante weggeht. Das ist der große Nachteil des Hyperwürfels: Wenn man
ihn ausbauen will, muß man die Knotenzahl immer gleich verdoppeln. Ein
Gitter kann man in kleineren Schritten vergrößern.

Ciao,
Martin




Mehr Informationen über die Mailingliste linux-l