1 Einführung.- 1.1 Allgemeines.- 1.2 Parallelrechner.- 1.3 Übermittlungssysteme.- 1.4 Multiplexverfahren.- 1.5 Transfermodi.- 1.6 Klassifikation von Kommunikationssystemen.- 1.7 Protokoll-Referenzmodelle.- 1.7.1 ISO-OSI-Schichtenmodell.- 1.7.2 Protokoll-Referenzmodell des Breitband-ISDN (B-ISDN).- 2 Unterscheidungsmerkmale.- 2.1 Topologie.- 2.1.1 Direkte Netze.- 2.1.2 Indirekte Netze.- 2.2 Topologische Klassifikationen.- 2.2.1 Durchmesser.- 2.2.2 Grad und Regularität.- 2.2.3 Bisektionsweite.- 2.2.4 Symmetrie.- 2.2.5 Skalierbarkeit.- 2.2.6 Permutationsmöglichkeiten.- 2.2.7 Partitionierbarkeit.- 2.2.8 Plättbarkeit.- 2.2.9 Teilgraphen, Schleifen und Einbettung.- 2.3 Schnittstellenstruktur.- 2.3.1 Schnittstellen in direkten Netzen.- 2.3.2 Schnittstellen in indirekten Netzen.- 2.3.3 Kommunikationsprozessoren.- 2.4 Operationsmodus.- 2.5 Kommunikationsflexibilität.- 2.6 Kontrollstrategie.- 2.7 Vermittlungsverfahren und Datentransport.- 2.8 Konfliktauflösung.- 2.9 Router- und Koppelelement-Architektur.- 2.9.1 Kontrollstrategie.- 2.9.2 Verbindungsstruktur.- 2.10 Testbarkeit und Fehlertoleranz.- 2.11 Technologische Realisierung.- 3 Grundlagen direkter Netze.- 3.1 Einfache und hierarchische Busse.- 3.1.1 Allgemeines.- 3.1.2 Datentransfer auf Prozessorbussen.- 3.1.3 Bus-Arbitrierung.- 3.1.4 Mehrfach-Bussysteme.- 3.1.5 Hierarchische Bussysteme.- 3.2 Ring-Netze und lineare Anordnungen.- 3.2.1 Grundlagen.- 3.2.2 Token-Ringe.- 3.2.3 Register-Insertion-Ringe.- 3.2.4 SCI-Ring.- 3.2.5 Lineare Anordnungen.- 3.2.6 Chordale Ringe.- 3.3 Zwei- und dreidimensionale Gitter-Netze.- 3.3.1 Gitter mit Grad 4.- 3.3.2 Gitter höheren Grades.- 3.4 Bäume und Pyramiden.- 3.4.1 Binäre und k-fache Bäume.- 3.4.2 Ring-erweiterte Bäume.- 3.4.3 Hyper-Baum.- 3.4.4 Fette Bäume.- 3.4.5 Pyramiden.- 3.4.6 Baumgitter.- 3.5 Direktes Shuffle-Exchange-Netz.- 3.6 DeBruijn-Netze.- 3.7 PM2i-Netze.- 3.8 Cube-Netze.- 3.9 Modifizierte Cube-Netze.- 3.9.1 Verdrehte und gekreuzte Cube-Netze.- 3.9.2 Erweiterte und gefaltete Cube-Netze.- 3.9.3 Unvollständige Cube-Netze.- 3.10 Cube-Connected-Cycles-Netze.- 3.11 Vollständige Vermaschung.- 3.12 Ubergreifende Klassifizierungen.- 3.12.1 k-fache n-Cube-Netze.- 3.12.2 Cayley-Graphen.- 4 Eigenschaften direkter Netze.- 4.1 Partitionierung.- 4.1.1 Partitionierung in MSIMD-Systemen.- 4.1.2 Partitionierung in MIMD-Systemen.- 4.2 Verbindungsfunktionen als Abbildungen und Permutationen.- 4.3 Zyklusnotation für Permutationen.- 4.3.1 Grundlagen.- 4.3.2 Auswirkungen von Aktivierung und Maskierung.- 4.3.3 Anwendungsbeispiele.- 4.4 Partitionierung direkter Permutationsnetze.- 4.4.1 Grundlagen.- 4.4.2 Partitionierung des Cube-Netzes.- 4.4.3 Partitionierung des PM2i-Netzes.- 4.5 Emulation in direkten Netzen.- 4.5.1 Einführung.- 4.5.2 Emulation des Cube-Netzes durch das PM2i-Netz.- 4.5.3 Emulation des Cube-Netzes durch das Shuffle-Exchange-Netz.- 4.6 Einbettung.- 4.6.1 Grundlagen.- 4.6.2 Einbettung eines Ringes im Cube-Netz.- 4.6.3 Einbettung von Gittern im Cube-Netz.- 4.6.4 Einbettung von binären Bäumen in Gittern.- 4.6.5 Einbettung binärer Bäume in Cube-Netzen.- 5 Datentransport und Wegsuche in direkten Netzen.- 5.1 Überblick.- 5.1.1 Kommunikationszeit.- 5.1.2 Virtuelle Kanäle.- 5.1.3 Mad-Postman-Routing.- 5.1.4 Deadlock und Livelock.- 5.1.5 Klassifikation von Wegsuch-Verfahren.- 5.2 Deterministisches Routing in direkten Netzen.- 5.2.1 XY-Routing.- 5.2.2 e-Cube-Algorithmus.- 5.3 Adaptives Routing in direkten Netzen.- 5.3.1 Adaptives umwegloses Routing mit progressiver Wegauswahl.- 5.3.1.1 Idle-Algorithmus.- 5.3.1.2 Double-Y-Channel-Routing.- 5.3.1.3 Duato´s Methodik.- 5.3.1.4 Adaptives Mad-Postman-Routing.- 5.3.2 Adaptives umwegbehaftetes Routing mit progressiver Wegauswahl.- 5.3.2.1 A1-Algorithmus.- 5.3.2.2 Wegsuche mit statischer und dynamischer Dimensionsumkehr.- 5.3.2.3 Turn-Modell.- 5.3.3 Backtracking adaptives Routing.- 5.3.3.1 Vollständige profitable Suche.- 5.3.3.2 Vollständige umwegbehaftete Suche.- 5.3.3.3 Two-phase misrouting backtracking.- 5.4 Zusammenfassung.- 6 Grundlagen indirekter Netze.- 6.1 Überblick.- 6.2 Einstufige indirekte Netze.- 6.2.1 Crossbar-Netz.- 6.2.2 Einstufiges Shuffle-Exchange-Netz.- 6.3 Mehrstufige Einpfadnetze.- 6.3.1 Banyan-Netz.- 6.3.2 Delta-Netz.- 6.3.3 Generalized-Cube-Netz.- 6.3.3.1 Topologie.- 6.3.3.2 Broadcast und Multicast.- 6.3.3.3 Permutationen.- 6.3.3.4 Partitionierung.- 6.3.3.5 Routing.- 6.3.4 Topologisch äquivalente Netze.- 6.3.4.1 Überblick.- 6.3.4.2 Omega-Netz.- 6.3.4.3 Indirect-Binary-n-Cube-Netz.- 6.3.4.4 Baseline-Netz.- 6.3.4.5 Flip-Netz.- 6.4 Datenmanipulatoren.- 6.4.1 Datenmanipulator nach Feng.- 6.4.2 Augmented Data Manipulator und Inverse Augmented Data Manipulator.- 6.4.2.1 Eigenschaften der Netze.- 6.4.2.2 Routing in ADM-Netzen.- 6.5 Indirekte Netze mit interner Datenoperation.- 6.5.1 Fetch-and-Add-Netze.- 6.5.2 Fetch-and-F-Netze.- 6.5.3 Kombinierende Netze.- 7 Blockierungsfreie und rearrangierbare Netze.- 7.1 Einführung.- 7.2 Blockierungsfreie Clos-Netze.- 7.3 Rearrangierbare Clos-Netze.- 7.4 Rekursive Konstruktion rearrangierbarer Netze.- 7.4.1 Konstruktion von Beneš-Netzen.- 7.4.2 Wegsuche im Beneš-Netz.- 7.5 Rekursive Konstruktion blockierungsfreier Netze.- 7.6 Blockierungsfreie Multicast-Netze.- 7.6.1 Grundlegende Architektur.- 7.6.2 Rekursive Konstruktion von Superkonzentratoren.- 7.6.3 Verteilnetze.- 7.6.4 Kopiernetze.- 7.6.5 Multicast-Netze.- 7.6.6 Das Pippenger Multicast-Netz.- 7.7 Selbstroutende Permutationsnetze.- 7.7.1 Allgemeines.- 7.7.2 Batcher-Banyan-Netze.- 8 Koppelelementarchitekturen und Realisierungsaspekte.- 8.1 Koppelelemente mit Eingangspufferung.- 8.2 Koppelelemente mit Ausgangspufferung.- 8.2.1 Busbasierte Koppelelemente.- 8.2.2 Ringbasierte Koppelelemente.- 8.2.3 Paketflußsteuerung in Block-Netzen.- 8.3 Koppelelemente mit verteilter Pufferung.- 8.4 Koppelelemente mit Zentralpufferung.- 8.4.1 Zentralpufferorganisation mit paralleler Pufferstruktur.- 8.4.2 Zentralpufferorganisation mit Schieberegisterstruktur.- 8.5 Prioritätsmechanismen in ATM-Koppelelementen.- 8.5.1 Wegetrennung.- 8.5.2 Getrennte Pufferung.- 8.5.3 Verdrängungssystem.- 8.5.4 Schwellwertverfahren.- 8.6 Koppelelemente für kombinierende Netze.- 9 Optische Verbindungsnetze.- 9.1 Einführung.- 9.2 Grundlagen und Technologie optischer Übertragung.- 9.3 Klassifikation optischer Netze.- 9.4 Broadcast-and-Select-Netze.- 9.4.1 Einschritt-Netze.- 9.4.1.1 Grundprinzip.- 9.4.1.2 Optische Koppler.- 9.4.1.3 Veränderliche Laser und optische Filter.- 9.4.1.4 Klassifizierung von Einschritt-Netzen.- 9.4.2 Mehrschritt-Netze.- 9.5 Wavelength-Routing-Netze.- 9.5.1 Statische Routingknoten.- 9.5.2 Dynamische Routingknoten.- 9.6 Optische Schaltelemente.- 9.6.1 Waveguide-Schaltelemente.- 9.6.1.1 Elektrische Steuerung.- 9.6.1.2 Optische Steuerung.- 9.6.2 Free-Space-Schaltelemente.- 9.6.3 Optische Pufferung.- 9.7 Free-Space-Verbindungsstrukturen.- 9.8 Ausblick.- 10 Fehlertoleranz und Test von Netzen.- 10.1 Grundlagen.- 10.1.1 Motivation.- 10.1.2 Fehlervermeidung.- 10.1.3 Fehlerbeherrschung.- 10.1.3.1 Fehlersichere Systeme.- 10.1.3.2 Fehlertolerante Systeme.- 10.1.4 Fehlerakkumulation.- 10.1.5 Fehlerfortpflanzung und Fehlerisolation.- 10.1.6 Erkennung und Lokalisierung von Fehlern.- 10.2 Fehler und Fehlermodelle.- 10.2.1 Einführung.- 10.2.2 Klassifikation.- 10.2.3 Auswirkungen auf fehlerbeherrschende Systeme.- 10.2.4 Funktionale Fehlermodelle.- 10.2.5 Schaltungstechnische Fehlermodelle.- 10.2.5.1 Haftfehler.- 10.2.5.2 Kurzschlußfehler.- 10.2.5.3 Offene Leitungen.- 10.2.6 Testerzeugung und Fehlerbehebung.- 10.3 Maßnahmen der Fehlererkennung, Fehlermaskierung und Fehlerbehebung.- 10.3.1 Codierung.- 10.3.2 Protokoll-Sicherung.- 10.3.3 Reserve zur Fehlerbehebung.- 10.3.4 Mehrfach-Redundanz zur Fehlerkompensation.- 10.3.5 Selbsttestende Logik.- 10.4 Fehlertolerante direkte Netze.- 10.5 Fehlertolerante indirekte Netze.- 10.5.1 Überblick und Methoden.- 10.5.2 Fehlermodelle.- 10.5.3 Extra-Stage-Cube-Netz.- 10.5.3.1 Broadcast im Extra-Stage-Cube-Netz.- 10.5.3.2 Routing im Extra-Stage-Cube-Netz.- 10.5.4 Multipath-Omega-Netz.- 10.5.5 F-Netz.- 10.5.6 Erweitertes IADM-Netz.- 10.5.7 Augmented-Shuffle-Exchange-Netz.- 10.5.8 Indra-Netz.- 10.5.9 Dynamisches-Redundanz-Netz.- 10.5.9.1 Routing im DR-Netz.- 10.5.9.2 Reduziertes DR-Netz (RDR-Netz).- 10.6 Test von Netzen.- 10.6.1 Testmethoden ohne Hardwareunterstützung.- 10.6.1.1 Durchschaltevermittelnde Netze.- 10.6.1.2 Paketvermittelnde Netze.- 10.6.2 Testmethoden mit Hardwareunterstützung.- 10.6.2.1 Testhilfen in VLSI-Schaltungen.- 10.6.2.2 Testhilfen in VLSI-Systemen.- 10.6.2.3 Polynomisches Testen.- 11 Fallbeispiele von Kommunikations- und Parallelrechnersystemen.- 11.1 ATM-Systeme.- 11.1.1 Koppelelemente mit verallgemeinerten Eingangspuffern.- 11.1.2 Koppelelemente mit Zentralpuffer.- 11.2 Parallelrechnersysteme.- 11.2.1 Direkte Netze.- 11.2.1.1 Hypercubes.- 11.2.1.2 2-dimensionale Gitternetze.- 11.2.1.3 3-dimensionale Gittemetze.- 11.2.1.4 VLSI-Prozessorfelder.- 11.2.2 Indirekte Netze.- 11.2.2.1 Einpfadnetze.- 11.2.2.2 Mehrpfadnetze.- 11.2.3 Hierarchische Netze.- 11.2.4 Netzkombinationen.- 11.2.5 Transputersysteme.- 12 Leistungsbewertung von Verbindungsnetzen.- 12.1 Überblick.- 12.2 Leistungsmaße.- 12.2.1 Strukturelle/Verkehrsunabhängige Kriterien.- 12.2.2 Verkehrsabhängige Leistungsmaße.- 12.2.2.1 Durchschaltevermittelnde Netze.- 12.2.2.2 Paketvermittelnde Netze.- 12.3 Verkehrsmodelle.- 12.3.1 Allgemeines.- 12.3.2 Verbindungsverteilung.- 12.3.2.1 Gleichverteilter Verkehr.- 12.3.2.2 Lokaler Verkehr.- 12.3.2.3 Statischer Hot-Spot-Verkehr.- 12.3.2.4 Dynamischer Hot-Spot-Verkehr.- 12.3.2.5 Permutationsverkehr.- 12.3.2.6 M u lticast-Verkehr.- 12.3.2.7 Single-Source-Single-Destination-Verkehr (SSSD).- 12.3.2.8 Prioritätsverkehr.- 12.3.2.9 Kombinierter Verkehr.- 12.3.3 Verkehrsratenerzeugung.- 12.4 Verkehrstheoretische Methoden der Leistungsbewertung.- 12.4.1 Zufallsvariable.- 12.4.2 Verteilungen.- 12.4.3 Prozesse und Theoreme.- 12.5 Analytische Leistungsbewertung gepufferter Koppelelemente.- 12.5.1 Ausgangspuffer.- 12.5.2 Eingangspuffer.- 12.5.2.1 Vernachlässigung des HOL-Effektes.- 12.5.2.2 Berücksichtigung des HOL-Effektes.- 12.5.3 Analyse mehrstufiger Netze.- 12.6 Bewertung durch Simulation.- 12.6.1 Allgemeines.- 12.6.2 Statistische Genauigkeit, Zufallszahlen, Aufwärmzyklen.- 12.6.3 Simulatorstrukturen.- 12.6.4 Aspekte der parallelen Simulation.- 12.6.4.1 Konventionelle Ansätze.- 12.6.4.2 Parallele ereignisgesteuerte Simulation.- 12.6.4.3 Parallele zeitgesteuerte Simulation.- 12.6.5 Simulationen für seltene Ereignisse.- 12.7 Simulativer Leistungsvergleich von Koppelelementen und Verbindungsnetzen.- 12.7.1 Leistung unter gleichverteiltem Verkehr.- 12.7.2 Leistung unter Hot-Spot-Verkehr.- 12.7.2.1 Statischer Hot-Spot-Verkehr.- 12.7.2.2 Dynamischer Hot-Spot-Verkehr.
Bei Parallelrechnern und Breitbandübermittlungssystemen wird eine effiziente Kommunikation durch Verbindungsnetze sichergestellt; die Netze beeinflussen die Leistungsfähigkeit der Systeme entscheidend. - Dieses Buch will fortgeschrittenen Studenten und Fachleuten im Bereich der Rechnerarchitektur und Kommunikationssysteme Grundlagen und vertiefende Kenntnisse über Strukturen, Leistungsbewertung und Realisierung von Verbindungsnetzen unterschiedlicher Komplexität vermitteln. Aus dem Inhalt: Einsatzbereiche - Klassifikationen - Statische und dynamische Netzwerke - Blockierungsfreie und rearrangierbare Netze - Fehlertolerante Netze - Testmethoden - Realisierungsaspekte - Deterministisches und adaptives Routing - Verkehrsmodelle - Verkehrstheoretische Leistungsbewertung - Simulation von Netzen - Fallbeispiele "... Endlich liegt ein fundiertes umfassendes und im höchsten Maße kompetentes Buch zum Thema Koppelnetze vor. In einer Zeit, in der die Vermittlungstechnik durch Techniken wie ATM, Switched Networks oder Photonische Netze immer aktueller wird, ist ein so solides und umfassendes Werk sehr zu begrüßen." NET 1/2 '97 "... Den Autoren ist es gelungen, ein umfangreiches Gebiet der Informationstechnik in einem einheitlichen Ansatz umfassend darzustellen. Das Buch eignet sich daher nicht nur als Begleitmaterial zu Lehrveranstaltungen, sondern es kann auch dem Praktiker und dem Forscher als Nachschlagewerk empfohlen werden." F.Lehmann. it + ti Informationstechnik und Technische Informatik, München
Das Gebiet der Verbindungsnetze kann bereits auf ein Jahrhundert Geschichte zurückblicken: nach der Erfindung der automatischen Verbindungssteuerung haben Koppelnetze in der Vermittlungstechnik zu der beispiellosen Ausbreitung der Telekommunikation geführt. Ihre Bedeutung war so groß, daß die wesentlichsten Kosten der Vermittlungssysteme über viele Jahrzehnte durch die Koppelnetze ver ursacht wurden; die Optimierung ihrer Strukturen und Steuerungsformen war des halb eine der wichtigsten technischen Herausforderungen. Erst mit der digitalen Zeitmultiplextechnik und ihrer VLSI-Realisierung konnten Koppelnetze kostengünstig realisiert werden. Mit der zellbasierten ATM-Vermittlungstechnik gewannen sie in den letzten Jahren in der Breitband-Vermittlungstechnik allerdings zum zweiten Male eine zentrale Bedeutung. Gleiches gilt für die sich abzeichnende photonische Ver mittlung. Der zweite Ursprung der Verbindungsnetze ist wesentlich jünger und mit dem Übergang von einfachen busbasierten Rechnerstrukturen hin zu massiv parallelen Rechnerarchitekturen verbunden. In den letzten zwei Jahrzehnten hat sich eine Vielzahl von Verbindungsnetztypen herausgebildet, welche in den ersten Parallel rechnem auch zum Einsatz gekommen sind. Bedingt durch das in beiden Anwendungs feldem, der ATM-basierten Breitbandvermittlung und den Parallelrechnem, gleicher maßen angewandte Paketvermittlungsprinzip sind die entstandenen Verbindungs netzstrukturen sehr verwandt, ihre Entwicklungen haben sich gegenseitig stark be fruchtet.
1 Einführung.- 1.1 Allgemeines.- 1.2 Parallelrechner.- 1.3 Übermittlungssysteme.- 1.4 Multiplexverfahren.- 1.5 Transfermodi.- 1.6 Klassifikation von Kommunikationssystemen.- 1.7 Protokoll-Referenzmodelle.- 1.7.1 ISO-OSI-Schichtenmodell.- 1.7.2 Protokoll-Referenzmodell des Breitband-ISDN (B-ISDN).- 2 Unterscheidungsmerkmale.- 2.1 Topologie.- 2.1.1 Direkte Netze.- 2.1.2 Indirekte Netze.- 2.2 Topologische Klassifikationen.- 2.2.1 Durchmesser.- 2.2.2 Grad und Regularität.- 2.2.3 Bisektionsweite.- 2.2.4 Symmetrie.- 2.2.5 Skalierbarkeit.- 2.2.6 Permutationsmöglichkeiten.- 2.2.7 Partitionierbarkeit.- 2.2.8 Plättbarkeit.- 2.2.9 Teilgraphen, Schleifen und Einbettung.- 2.3 Schnittstellenstruktur.- 2.3.1 Schnittstellen in direkten Netzen.- 2.3.2 Schnittstellen in indirekten Netzen.- 2.3.3 Kommunikationsprozessoren.- 2.4 Operationsmodus.- 2.5 Kommunikationsflexibilität.- 2.6 Kontrollstrategie.- 2.7 Vermittlungsverfahren und Datentransport.- 2.8 Konfliktauflösung.- 2.9 Router- und Koppelelement-Architektur.- 2.9.1 Kontrollstrategie.- 2.9.2 Verbindungsstruktur.- 2.10 Testbarkeit und Fehlertoleranz.- 2.11 Technologische Realisierung.- 3 Grundlagen direkter Netze.- 3.1 Einfache und hierarchische Busse.- 3.1.1 Allgemeines.- 3.1.2 Datentransfer auf Prozessorbussen.- 3.1.3 Bus-Arbitrierung.- 3.1.4 Mehrfach-Bussysteme.- 3.1.5 Hierarchische Bussysteme.- 3.2 Ring-Netze und lineare Anordnungen.- 3.2.1 Grundlagen.- 3.2.2 Token-Ringe.- 3.2.3 Register-Insertion-Ringe.- 3.2.4 SCI-Ring.- 3.2.5 Lineare Anordnungen.- 3.2.6 Chordale Ringe.- 3.3 Zwei- und dreidimensionale Gitter-Netze.- 3.3.1 Gitter mit Grad 4.- 3.3.2 Gitter höheren Grades.- 3.4 Bäume und Pyramiden.- 3.4.1 Binäre und k-fache Bäume.- 3.4.2 Ring-erweiterte Bäume.- 3.4.3 Hyper-Baum.- 3.4.4 Fette Bäume.- 3.4.5 Pyramiden.- 3.4.6 Baumgitter.- 3.5 Direktes Shuffle-Exchange-Netz.- 3.6 DeBruijn-Netze.- 3.7 PM2i-Netze.- 3.8 Cube-Netze.- 3.9 Modifizierte Cube-Netze.- 3.9.1 Verdrehte und gekreuzte Cube-Netze.- 3.9.2 Erweiterte und gefaltete Cube-Netze.- 3.9.3 Unvollständige Cube-Netze.- 3.10 Cube-Connected-Cycles-Netze.- 3.11 Vollständige Vermaschung.- 3.12 Ubergreifende Klassifizierungen.- 3.12.1 k-fache n-Cube-Netze.- 3.12.2 Cayley-Graphen.- 4 Eigenschaften direkter Netze.- 4.1 Partitionierung.- 4.1.1 Partitionierung in MSIMD-Systemen.- 4.1.2 Partitionierung in MIMD-Systemen.- 4.2 Verbindungsfunktionen als Abbildungen und Permutationen.- 4.3 Zyklusnotation für Permutationen.- 4.3.1 Grundlagen.- 4.3.2 Auswirkungen von Aktivierung und Maskierung.- 4.3.3 Anwendungsbeispiele.- 4.4 Partitionierung direkter Permutationsnetze.- 4.4.1 Grundlagen.- 4.4.2 Partitionierung des Cube-Netzes.- 4.4.3 Partitionierung des PM2i-Netzes.- 4.5 Emulation in direkten Netzen.- 4.5.1 Einführung.- 4.5.2 Emulation des Cube-Netzes durch das PM2i-Netz.- 4.5.3 Emulation des Cube-Netzes durch das Shuffle-Exchange-Netz.- 4.6 Einbettung.- 4.6.1 Grundlagen.- 4.6.2 Einbettung eines Ringes im Cube-Netz.- 4.6.3 Einbettung von Gittern im Cube-Netz.- 4.6.4 Einbettung von binären Bäumen in Gittern.- 4.6.5 Einbettung binärer Bäume in Cube-Netzen.- 5 Datentransport und Wegsuche in direkten Netzen.- 5.1 Überblick.- 5.1.1 Kommunikationszeit.- 5.1.2 Virtuelle Kanäle.- 5.1.3 Mad-Postman-Routing.- 5.1.4 Deadlock und Livelock.- 5.1.5 Klassifikation von Wegsuch-Verfahren.- 5.2 Deterministisches Routing in direkten Netzen.- 5.2.1 XY-Routing.- 5.2.2 e-Cube-Algorithmus.- 5.3 Adaptives Routing in direkten Netzen.- 5.3.1 Adaptives umwegloses Routing mit progressiver Wegauswahl.- 5.3.1.1 Idle-Algorithmus.- 5.3.1.2 Double-Y-Channel-Routing.- 5.3.1.3 Duato s Methodik.- 5.3.1.4 Adaptives Mad-Postman-Routing.- 5.3.2 Adaptives umwegbehaftetes Routing mit progressiver Wegauswahl.- 5.3.2.1 A1-Algorithmus.- 5.3.2.2 Wegsuche mit statischer und dynamischer Dimensionsumkehr.- 5.3.2.3 Turn-Modell.- 5.3.3 Backtracking adaptives Routing.- 5.3.3.1 Vollständige profitable Suche.- 5.3.3.2 Vollständige umwegbehaftete Suche.- 5.3.3.3 Two-phase misrou
Inhaltsverzeichnis
1 Einführung.- 1.1 Allgemeines.- 1.2 Parallelrechner.- 1.3 Übermittlungssysteme.- 1.4 Multiplexverfahren.- 1.5 Transfermodi.- 1.6 Klassifikation von Kommunikationssystemen.- 1.7 Protokoll-Referenzmodelle.- 1.7.1 ISO-OSI-Schichtenmodell.- 1.7.2 Protokoll-Referenzmodell des Breitband-ISDN (B-ISDN).- 2 Unterscheidungsmerkmale.- 2.1 Topologie.- 2.1.1 Direkte Netze.- 2.1.2 Indirekte Netze.- 2.2 Topologische Klassifikationen.- 2.2.1 Durchmesser.- 2.2.2 Grad und Regularität.- 2.2.3 Bisektionsweite.- 2.2.4 Symmetrie.- 2.2.5 Skalierbarkeit.- 2.2.6 Permutationsmöglichkeiten.- 2.2.7 Partitionierbarkeit.- 2.2.8 Plättbarkeit.- 2.2.9 Teilgraphen, Schleifen und Einbettung.- 2.3 Schnittstellenstruktur.- 2.3.1 Schnittstellen in direkten Netzen.- 2.3.2 Schnittstellen in indirekten Netzen.- 2.3.3 Kommunikationsprozessoren.- 2.4 Operationsmodus.- 2.5 Kommunikationsflexibilität.- 2.6 Kontrollstrategie.- 2.7 Vermittlungsverfahren und Datentransport.- 2.8 Konfliktauflösung.- 2.9 Router- und Koppelelement-Architektur.- 2.9.1 Kontrollstrategie.- 2.9.2 Verbindungsstruktur.- 2.10 Testbarkeit und Fehlertoleranz.- 2.11 Technologische Realisierung.- 3 Grundlagen direkter Netze.- 3.1 Einfache und hierarchische Busse.- 3.1.1 Allgemeines.- 3.1.2 Datentransfer auf Prozessorbussen.- 3.1.3 Bus-Arbitrierung.- 3.1.4 Mehrfach-Bussysteme.- 3.1.5 Hierarchische Bussysteme.- 3.2 Ring-Netze und lineare Anordnungen.- 3.2.1 Grundlagen.- 3.2.2 Token-Ringe.- 3.2.3 Register-Insertion-Ringe.- 3.2.4 SCI-Ring.- 3.2.5 Lineare Anordnungen.- 3.2.6 Chordale Ringe.- 3.3 Zwei- und dreidimensionale Gitter-Netze.- 3.3.1 Gitter mit Grad 4.- 3.3.2 Gitter höheren Grades.- 3.4 Bäume und Pyramiden.- 3.4.1 Binäre und k-fache Bäume.- 3.4.2 Ring-erweiterte Bäume.- 3.4.3 Hyper-Baum.- 3.4.4 Fette Bäume.- 3.4.5 Pyramiden.- 3.4.6 Baumgitter.- 3.5 Direktes Shuffle-Exchange-Netz.- 3.6 DeBruijn-Netze.- 3.7 PM2i-Netze.- 3.8 Cube-Netze.- 3.9 Modifizierte Cube-Netze.- 3.9.1 Verdrehte und gekreuzte Cube-Netze.- 3.9.2 Erweiterte und gefaltete Cube-Netze.- 3.9.3 Unvollständige Cube-Netze.- 3.10 Cube-Connected-Cycles-Netze.- 3.11 Vollständige Vermaschung.- 3.12 Ubergreifende Klassifizierungen.- 3.12.1 k-fache n-Cube-Netze.- 3.12.2 Cayley-Graphen.- 4 Eigenschaften direkter Netze.- 4.1 Partitionierung.- 4.1.1 Partitionierung in MSIMD-Systemen.- 4.1.2 Partitionierung in MIMD-Systemen.- 4.2 Verbindungsfunktionen als Abbildungen und Permutationen.- 4.3 Zyklusnotation für Permutationen.- 4.3.1 Grundlagen.- 4.3.2 Auswirkungen von Aktivierung und Maskierung.- 4.3.3 Anwendungsbeispiele.- 4.4 Partitionierung direkter Permutationsnetze.- 4.4.1 Grundlagen.- 4.4.2 Partitionierung des Cube-Netzes.- 4.4.3 Partitionierung des PM2i-Netzes.- 4.5 Emulation in direkten Netzen.- 4.5.1 Einführung.- 4.5.2 Emulation des Cube-Netzes durch das PM2i-Netz.- 4.5.3 Emulation des Cube-Netzes durch das Shuffle-Exchange-Netz.- 4.6 Einbettung.- 4.6.1 Grundlagen.- 4.6.2 Einbettung eines Ringes im Cube-Netz.- 4.6.3 Einbettung von Gittern im Cube-Netz.- 4.6.4 Einbettung von binären Bäumen in Gittern.- 4.6.5 Einbettung binärer Bäume in Cube-Netzen.- 5 Datentransport und Wegsuche in direkten Netzen.- 5.1 Überblick.- 5.1.1 Kommunikationszeit.- 5.1.2 Virtuelle Kanäle.- 5.1.3 Mad-Postman-Routing.- 5.1.4 Deadlock und Livelock.- 5.1.5 Klassifikation von Wegsuch-Verfahren.- 5.2 Deterministisches Routing in direkten Netzen.- 5.2.1 XY-Routing.- 5.2.2 e-Cube-Algorithmus.- 5.3 Adaptives Routing in direkten Netzen.- 5.3.1 Adaptives umwegloses Routing mit progressiver Wegauswahl.- 5.3.1.1 Idle-Algorithmus.- 5.3.1.2 Double-Y-Channel-Routing.- 5.3.1.3 Duatös Methodik.- 5.3.1.4 Adaptives Mad-Postman-Routing.- 5.3.2 Adaptives umwegbehaftetes Routing mit progressiver Wegauswahl.- 5.3.2.1 A1-Algorithmus.- 5.3.2.2 Wegsuche mit statischer und dynamischer Dimensionsumkehr.- 5.3.2.3 Turn-Modell.- 5.3.3 Backtracking adaptives Routing.- 5.3.3.1 Vollständige profitable Suche.- 5.3.3.2 Vollständige umwegbehaftete Suche.- 5.3.3.3 Two-phase misrouting backtracking.- 5.4 Zusammenfassung.- 6 Grundlagen indirekter Netze.- 6.1 Überblick.- 6.2 Einstufige indirekte Netze.- 6.2.1 Crossbar-Netz.- 6.2.2 Einstufiges Shuffle-Exchange-Netz.- 6.3 Mehrstufige Einpfadnetze.- 6.3.1 Banyan-Netz.- 6.3.2 Delta-Netz.- 6.3.3 Generalized-Cube-Netz.- 6.3.3.1 Topologie.- 6.3.3.2 Broadcast und Multicast.- 6.3.3.3 Permutationen.- 6.3.3.4 Partitionierung.- 6.3.3.5 Routing.- 6.3.4 Topologisch äquivalente Netze.- 6.3.4.1 Überblick.- 6.3.4.2 Omega-Netz.- 6.3.4.3 Indirect-Binary-n-Cube-Netz.- 6.3.4.4 Baseline-Netz.- 6.3.4.5 Flip-Netz.- 6.4 Datenmanipulatoren.- 6.4.1 Datenmanipulator nach Feng.- 6.4.2 Augmented Data Manipulator und Inverse Augmented Data Manipulator.- 6.4.2.1 Eigenschaften der Netze.- 6.4.2.2 Routing in ADM-Netzen.- 6.5 Indirekte Netze mit interner Datenoperation.- 6.5.1 Fetch-and-Add-Netze.- 6.5.2 Fetch-and-F-Netze.- 6.5.3 Kombinierende Netze.- 7 Blockierungsfreie und rearrangierbare Netze.- 7.1 Einführung.- 7.2 Blockierungsfreie Clos-Netze.- 7.3 Rearrangierbare Clos-Netze.- 7.4 Rekursive Konstruktion rearrangierbarer Netze.- 7.4.1 Konstruktion von Beneš-Netzen.- 7.4.2 Wegsuche im Beneš-Netz.- 7.5 Rekursive Konstruktion blockierungsfreier Netze.- 7.6 Blockierungsfreie Multicast-Netze.- 7.6.1 Grundlegende Architektur.- 7.6.2 Rekursive Konstruktion von Superkonzentratoren.- 7.6.3 Verteilnetze.- 7.6.4 Kopiernetze.- 7.6.5 Multicast-Netze.- 7.6.6 Das Pippenger Multicast-Netz.- 7.7 Selbstroutende Permutationsnetze.- 7.7.1 Allgemeines.- 7.7.2 Batcher-Banyan-Netze.- 8 Koppelelementarchitekturen und Realisierungsaspekte.- 8.1 Koppelelemente mit Eingangspufferung.- 8.2 Koppelelemente mit Ausgangspufferung.- 8.2.1 Busbasierte Koppelelemente.- 8.2.2 Ringbasierte Koppelelemente.- 8.2.3 Paketflußsteuerung in Block-Netzen.- 8.3 Koppelelemente mit verteilter Pufferung.- 8.4 Koppelelemente mit Zentralpufferung.- 8.4.1 Zentralpufferorganisation mit paralleler Pufferstruktur.- 8.4.2 Zentralpufferorganisation mit Schieberegisterstruktur.- 8.5 Prioritätsmechanismen in ATM-Koppelelementen.- 8.5.1 Wegetrennung.- 8.5.2 Getrennte Pufferung.- 8.5.3 Verdrängungssystem.- 8.5.4 Schwellwertverfahren.- 8.6 Koppelelemente für kombinierende Netze.- 9 Optische Verbindungsnetze.- 9.1 Einführung.- 9.2 Grundlagen und Technologie optischer Übertragung.- 9.3 Klassifikation optischer Netze.- 9.4 Broadcast-and-Select-Netze.- 9.4.1 Einschritt-Netze.- 9.4.1.1 Grundprinzip.- 9.4.1.2 Optische Koppler.- 9.4.1.3 Veränderliche Laser und optische Filter.- 9.4.1.4 Klassifizierung von Einschritt-Netzen.- 9.4.2 Mehrschritt-Netze.- 9.5 Wavelength-Routing-Netze.- 9.5.1 Statische Routingknoten.- 9.5.2 Dynamische Routingknoten.- 9.6 Optische Schaltelemente.- 9.6.1 Waveguide-Schaltelemente.- 9.6.1.1 Elektrische Steuerung.- 9.6.1.2 Optische Steuerung.- 9.6.2 Free-Space-Schaltelemente.- 9.6.3 Optische Pufferung.- 9.7 Free-Space-Verbindungsstrukturen.- 9.8 Ausblick.- 10 Fehlertoleranz und Test von Netzen.- 10.1 Grundlagen.- 10.1.1 Motivation.- 10.1.2 Fehlervermeidung.- 10.1.3 Fehlerbeherrschung.- 10.1.3.1 Fehlersichere Systeme.- 10.1.3.2 Fehlertolerante Systeme.- 10.1.4 Fehlerakkumulation.- 10.1.5 Fehlerfortpflanzung und Fehlerisolation.- 10.1.6 Erkennung und Lokalisierung von Fehlern.- 10.2 Fehler und Fehlermodelle.- 10.2.1 Einführung.- 10.2.2 Klassifikation.- 10.2.3 Auswirkungen auf fehlerbeherrschende Systeme.- 10.2.4 Funktionale Fehlermodelle.- 10.2.5 Schaltungstechnische Fehlermodelle.- 10.2.5.1 Haftfehler.- 10.2.5.2 Kurzschlußfehler.- 10.2.5.3 Offene Leitungen.- 10.2.6 Testerzeugung und Fehlerbehebung.- 10.3 Maßnahmen der Fehlererkennung, Fehlermaskierung und Fehlerbehebung.- 10.3.1 Codierung.- 10.3.2 Protokoll-Sicherung.- 10.3.3 Reserve zur Fehlerbehebung.- 10.3.4 Mehrfach-Redundanz zur Fehlerkompensation.- 10.3.5 Selbsttestende Logik.- 10.4 Fehlertolerante direkte Netze.- 10.5 Fehlertolerante indirekte Netze.- 10.5.1 Überblick und Methoden.- 10.5.2 Fehlermodelle.- 10.5.3 Extra-Stage-Cube-Netz.- 10.5.3.1 Broadcast im Extra-Stage-Cube-Netz.- 10.5.3.2 Routing im Extra-Stage-Cube-Netz.- 10.5.4 Multipath-Omega-Netz.- 10.5.5 F-Netz.- 10.5.6 Erweitertes IADM-Netz.- 10.5.7 Augmented-Shuffle-Exchange-Netz.- 10.5.8 Indra-Netz.- 10.5.9 Dynamisches-Redundanz-Netz.- 10.5.9.1 Routing im DR-Netz.- 10.5.9.2 Reduziertes DR-Netz (RDR-Netz).- 10.6 Test von Netzen.- 10.6.1 Testmethoden ohne Hardwareunterstützung.- 10.6.1.1 Durchschaltevermittelnde Netze.- 10.6.1.2 Paketvermittelnde Netze.- 10.6.2 Testmethoden mit Hardwareunterstützung.- 10.6.2.1 Testhilfen in VLSI-Schaltungen.- 10.6.2.2 Testhilfen in VLSI-Systemen.- 10.6.2.3 Polynomisches Testen.- 11 Fallbeispiele von Kommunikations- und Parallelrechnersystemen.- 11.1 ATM-Systeme.- 11.1.1 Koppelelemente mit verallgemeinerten Eingangspuffern.- 11.1.2 Koppelelemente mit Zentralpuffer.- 11.2 Parallelrechnersysteme.- 11.2.1 Direkte Netze.- 11.2.1.1 Hypercubes.- 11.2.1.2 2-dimensionale Gitternetze.- 11.2.1.3 3-dimensionale Gittemetze.- 11.2.1.4 VLSI-Prozessorfelder.- 11.2.2 Indirekte Netze.- 11.2.2.1 Einpfadnetze.- 11.2.2.2 Mehrpfadnetze.- 11.2.3 Hierarchische Netze.- 11.2.4 Netzkombinationen.- 11.2.5 Transputersysteme.- 12 Leistungsbewertung von Verbindungsnetzen.- 12.1 Überblick.- 12.2 Leistungsmaße.- 12.2.1 Strukturelle/Verkehrsunabhängige Kriterien.- 12.2.2 Verkehrsabhängige Leistungsmaße.- 12.2.2.1 Durchschaltevermittelnde Netze.- 12.2.2.2 Paketvermittelnde Netze.- 12.3 Verkehrsmodelle.- 12.3.1 Allgemeines.- 12.3.2 Verbindungsverteilung.- 12.3.2.1 Gleichverteilter Verkehr.- 12.3.2.2 Lokaler Verkehr.- 12.3.2.3 Statischer Hot-Spot-Verkehr.- 12.3.2.4 Dynamischer Hot-Spot-Verkehr.- 12.3.2.5 Permutationsverkehr.- 12.3.2.6 M u lticast-Verkehr.- 12.3.2.7 Single-Source-Single-Destination-Verkehr (SSSD).- 12.3.2.8 Prioritätsverkehr.- 12.3.2.9 Kombinierter Verkehr.- 12.3.3 Verkehrsratenerzeugung.- 12.4 Verkehrstheoretische Methoden der Leistungsbewertung.- 12.4.1 Zufallsvariable.- 12.4.2 Verteilungen.- 12.4.3 Prozesse und Theoreme.- 12.5 Analytische Leistungsbewertung gepufferter Koppelelemente.- 12.5.1 Ausgangspuffer.- 12.5.2 Eingangspuffer.- 12.5.2.1 Vernachlässigung des HOL-Effektes.- 12.5.2.2 Berücksichtigung des HOL-Effektes.- 12.5.3 Analyse mehrstufiger Netze.- 12.6 Bewertung durch Simulation.- 12.6.1 Allgemeines.- 12.6.2 Statistische Genauigkeit, Zufallszahlen, Aufwärmzyklen.- 12.6.3 Simulatorstrukturen.- 12.6.4 Aspekte der parallelen Simulation.- 12.6.4.1 Konventionelle Ansätze.- 12.6.4.2 Parallele ereignisgesteuerte Simulation.- 12.6.4.3 Parallele zeitgesteuerte Simulation.- 12.6.5 Simulationen für seltene Ereignisse.- 12.7 Simulativer Leistungsvergleich von Koppelelementen und Verbindungsnetzen.- 12.7.1 Leistung unter gleichverteiltem Verkehr.- 12.7.2 Leistung unter Hot-Spot-Verkehr.- 12.7.2.1 Statischer Hot-Spot-Verkehr.- 12.7.2.2 Dynamischer Hot-Spot-Verkehr.
Klappentext
Das Gebiet der Verbindungsnetze kann bereits auf ein Jahrhundert Geschichte zurückblicken: nach der Erfindung der automatischen Verbindungssteuerung haben Koppelnetze in der Vermittlungstechnik zu der beispiellosen Ausbreitung der Telekommunikation geführt. Ihre Bedeutung war so groß, daß die wesentlichsten Kosten der Vermittlungssysteme über viele Jahrzehnte durch die Koppelnetze ver ursacht wurden; die Optimierung ihrer Strukturen und Steuerungsformen war des halb eine der wichtigsten technischen Herausforderungen. Erst mit der digitalen Zeitmultiplextechnik und ihrer VLSI-Realisierung konnten Koppelnetze kostengünstig realisiert werden. Mit der zellbasierten ATM-Vermittlungstechnik gewannen sie in den letzten Jahren in der Breitband-Vermittlungstechnik allerdings zum zweiten Male eine zentrale Bedeutung. Gleiches gilt für die sich abzeichnende photonische Ver mittlung. Der zweite Ursprung der Verbindungsnetze ist wesentlich jünger und mit dem Übergang von einfachen busbasierten Rechnerstrukturen hin zu massiv parallelen Rechnerarchitekturen verbunden. In den letzten zwei Jahrzehnten hat sich eine Vielzahl von Verbindungsnetztypen herausgebildet, welche in den ersten Parallel rechnem auch zum Einsatz gekommen sind. Bedingt durch das in beiden Anwendungs feldem, der ATM-basierten Breitbandvermittlung und den Parallelrechnem, gleicher maßen angewandte Paketvermittlungsprinzip sind die entstandenen Verbindungs netzstrukturen sehr verwandt, ihre Entwicklungen haben sich gegenseitig stark be fruchtet.
