Knowledge & Learning

home *** CD-ROM | disk | FTP | other *** search

/ Knowledge & Learning / WISS_LERN.iso / doslern / computer / educard / bs___6.sti < prev next >

Wrap

Text File | 1992-03-09 | 92.3 KB | 2,208 lines

YCPAA #!!# - Rechnernetze - @CEInhalt @CPDas Thema von BS___6 sind Rechnernetze. Start mit ⌐Rechnernetz@BS___6¬ AHBAA #!!# Rechnernetz #!!# Netzwerk @HEEinführung @HB @HPVerbundsysteme@HB oder @HPNetze@HB kennt man aus den verschiedensten Bereichen. Typische Beispiele aus dem Bereich der Technik sind Versorgungsnetze, Telefonnetze, Verkehrsnetze. Ihnen allen ist gemeinsam, daß man sie durch zusammenhängende endliche Graphen beschreiben kann. Die Knoten der Graphen entsprechen den Verteiler- und Entscheidungs- zentren, die Kanten den Kommunikations- und Transportwegen. In @HPRechnernetzen@HB werden zwischen Netzknoten Nachrichten transportiert. Ein wesentlicher Unterschied zu anderen Netzen besteht darin, daß sich die Funktion der Netzknoten im Rechennetz nicht auf Schalt- oder Verteiler- funktionen beschränkt. Übermittlung von Nachrichten ist nicht die Haupt- aufgabe eines Rechnernetzes, sondern nur Begleitumstand der Auftrags- bearbeitungen, die in den Rechnersystemen der Netzknoten ablaufen. @HEDefinition @HB Ein @HPRechnernetz@HB ist ein loses gekoppeltes @HPMulticomputersystem@HB, bei dem einzelne Rechner (Rechnerknoten) räumlich getrennt sind. Die Kommunikation zwischen den Rechnerknoten erfolgt durch Nachrichtenaustausch auf der Grundlage von Protokollen. Es gibt Netze, bei denen die Rechnerknoten über große geographische Räume verteilt sind und die Kommunikation in der Regel über öffentliche Daten- übertragungs-Einrichtungen, unter Umständen auch über Satelliten, erfolgt. Bei anderen Netzen sind lokale Rechner miteinander verbunden. Die Rechnerknoten sind hier über spezielle Leitungen, zum Beispiel Koaxial- kabel, verbunden. @HEGründe für den Aufbau von Rechnernetzen @HB Für die Einrichtung von ⌐Rechnernetz@BS2¬en gibt es drei wesentliche Gründe: a) Erweiterung der @HPFunktionsbreite@HB der beteiligten autonomen Rechnersysteme (resource sharing) b) @HPLastenausgleich@HB zwischen den beteiligten autonomen Systemen zum Zweck verbesserter Antwortzeiten (load sharing) c) Erhöhung der @HPZuverlässigkeit@HB des Gesamtsystems @HBa) @HPErweiterung der Funktionsbreite@HB Durch Schaffung von Rechnernetzen stehen den einzelnen Rechnersystemen zusätzliche ⌐Betriebsmittel@BS1¬ bereit. Dies bietet die Möglichkeit zur: - gemeinsamen @HPDateibenutzung@HB (Vorteil gegenüber Kopieren von großen Dateien) - gemeinsamen @HPProgrammbenutzung@HB komplexe Programmsysteme können zentralisiert werden (Vorteile: verkürzte Ausführungszeiten, erhöhte Leistungsfähigkeit) - Befriedigung von Anforderungen großer @HPSpeicherkapazitäten@HB @HBb) @HPLastenausgleich@HB Das Ziel des Lastenausgleichs ist die Ausnutzung freier Kapazitäten und dadurch eine bessere Ausnutzung der beteiligten Systeme, woraus eine Verkürzung der Bearbeitungsdauer von Aufträgen folgt. c) @HPZuverlässigkeit@HB Die Zuverlässigkeit des Gesamtsystems ist höher als die Zuverlässig- keit eines einzelnen beteiligten Systems, da dessen Aufgaben umver- teilt werden können, wenn es ausfällt. weiter mit ⌐Kommunikationssysteme@BS___6¬ AHBAA #!!# Kommunikationssysteme @HEKommunikation in Rechnernetzen @HB Ein wesentlicher Teil eines ⌐Rechnernetz@BS___6¬es ist das Kommunikationssystem. Die Anforderungen an ein Kommunikationssystem beziehen sich auf folgende Eigenschaften: a) Übertragungsgeschwindigkeit bzw. -verzögerung b) ⌐Durchsatz@BS1¬ c) Übertragungskosten d) Zuverlässigkeit @HBa) @HPZeitverzögerung@HB Die Zeitverzögerung im Rechennetz setzt sich zusammen aus Wartezeiten auf das Freiwerden von Kommunikationskanälen und der Übertragungszeit für die Nachricht. Sie sollte sich höchstens in der Größenordnung der Übertragungszeit der Nachricht bewegen. b) @HPDurchsatz@HB Der Durchsatz eines Rechnernetzes ist stark verbunden mit der Über- tragungsgeschwindigkeit bzw. der Zeitverzögerung. Der mittlere Durchsatz setzt sich zusammen aus @HP_@HP - mittlere Nachrichtenlänge @HPb@HB in Bits - Anzahl der Nachrichten @HPm@HB im Netz - Zeitverzögerung @HPZ_jk@HB des Netzes in Sekunden, gemittelt über alle Nachrichten, die vom Knoten j zum Knoten k transportiert werden. @AO ╔═══════════════════════════════════╗ @HB @AO ║ _ m ║ @HB @AO ║ Mittlerer Durchsatz = b * ────── ║ @HB @AO ║ Z_jk ║ @HB @AO ╚═══════════════════════════════════╝ @HB c) @HPÜbertragungskosten@HB Hier gilt ähnliches wie bei den Verzögerungszeiten: Die Übertragungskosten sollten im "sinnvollen" Verhältnis zu den Bearbeitungskosten des jeweiligen Auftrags stehen. d) @HPZuverlässigkeit@HB Das Kommunikationssystem und damit das Rechnernetz sollte nicht durch Ausfall einzelner Übertragungswege funktionsunfähig werden. Wesentlich für die Zuverlässigkeit des Kommunikationssystems sind auch eine Fehlererkennungs- und Fehlerkorrektur-Möglichkeit beim Auftreten einzelner Übertragungsfehler. Fehlererkennung und -korrektur kann durch geeignete Kommunikationsprotokolle erreicht werden. @HEAufgaben des Kommunikationssystems @HB Die Aufgabe des Kommunikationssystems besteht in der Abwicklung der Informationsübertragung zwischen den autonomen Rechnern des Netzes, das heißt es ist für den Transport von Nachrichten von der Nachrichtenquelle zum Nachrichtenziel verantwortlich. Im einzelnen gehören dazu: a) die @HPSynchronisation@HB von exklusiven ⌐Betriebsmittel@BS1¬n, das heißt den gegenseitigen Ausschluß beim Zugriff auf globale Daten garantieren b) die @HPBereitstellung eines Nachrichtenweges@HB, das heißt der Aufbau eines physikalischen Übertragungsweges von der Quelle zum Ziel durch Bereitstellen und Zusammenschaltung der notwendigen Kommunikationskanäle c) die @HPNachrichtenweiterleitung@HB, der eigentliche Nachrichtentransport über die Kommunikationskanäle weiter mit ⌐Netz-Synchronisation@BS___6¬ AHBAA #!!# Netz-Synchronisation @EH Synchronisation in Rechnernetzen @HB Ein Beispiel für die Synchronisation in ⌐Rechnernetz@BS___6¬en, zum Zweck des gegenseitigen Ausschlusses beim gemeinsamen Zugriff auf ein exklusiv benutzbares Betriebsmittel, ist der Algorithmus von Ricart und Agrawala. @HEAlgorithmus von Ricart und Agrawala @HB Voraussetzungen: - Prozesse können nur durch Nachrichten kommunizieren, wobei jeder mit jedem in Kommunikation treten kann. - Die Arbeit in den Knoten und der Nachrichtenaustausch verlaufen ohne Störungen. - Die Übertragungsdauer ist völlig unvorhersehbar. Es kann also vorkommen, daß sich Nachrichten gegenseitig überholen. - Die Lösung soll symmetrisch sein, das heißt alle Knoten werden gleich behandelt. Es gibt keinen "Master", der mehr Rechte hat als andere Knoten. Idee: Jeder Knoten, der das kritische Gebiet betreten will, fragt bei allen anderen nach, ob er es darf (sendet REQUEST) und wartet auf deren Einwilligung (erhält REPLY). Ein Knoten kann nicht "Nein" sagen (seine Einwilligung nicht geben), sondern nur sein "Ja" (seine Einwilligung) verzögern. Er kann aus zwei Gründen verzögern: a) er selbst ist im kritischen Gebiet oder b) er hat sich um das kritische Gebiet beworben und Vorrang vor allen ihm bekannten Mitbewerbern. Er gibt seine Einwilligung im Fall a) erst dann, wenn er das kritische Gebiet verlassen hat und im Fall b) erst dann, wenn er das kritische Gebiet betreten und wieder verlassen hat. @HB Ein Knoten hat Vorrang, wenn ihm a) weniger Bewerbungen für das kritische Gebiet bekannt sind als seinen Mitbewerbern und er hat Vorrang, wenn b) die Anzahl der bekannten Bewerbungen gleich ist aber seine Knoten- Nummer kleiner ist, als die seiner Konkurrenten. Lokale Daten eines Knotens: - @HPme@HB : Knoten-Nummer des gerade betrachteten Knotens - @HPk@HB : Knoten-Nummer eines anderen Knotens - @HPhighest_seq_nr@HB : die größte Bewerberzahl, die dem gerade betrach- teten Knoten (me) bekannt ist - @HPhis_highest_seq_nr@HB : die größte Bewerberzahl, die dem Knoten mit der Nummer k bekannt ist @HBAlgorithmus (vereinfacht) fü alle N Knoten des Netzes: 1. Arbeit des Knotens: @HPBeantrage kritisches Gebiet@HB i) Sende an alle Knoten REQUEST (me, highest_seq_nr + 1) und warte dann, bis alle Einwilligungen (REPLY's) eingetroffen sind. ii) Eintritt, Arbeit, Verlassen des kritischen Gebietes iii) Schicke REPLY an alle Knoten, die zwischenzeitlich das kritische Gebiet im Netz beantragt haben, aber erst jetzt (nach meinem Verlassen des kritischen Gebietes) die Einwilligung erhalten können. @HB 2. Arbeit des Knotens: @HPBehandle erhaltenes REQUEST (k, his_highest_seq_nr)@HB i) highest_seq_nr := max (highest_seq_nr, hishighest_seq_nr) ii) Einwilligung (REPLY) an k verzögern, falls - me selbst im kritischen Gebiet ist bzw. - hinein will und Vorrang hat. Sonst sende sofort REPLY an k. 3. Arbeit des Knotens: @HPBehandle erhaltene REPLY's@HB Zähle die Anzahl der erhaltenen Einwilligungen (REPLY's) mit, um bei 1. i) entscheiden zu können. @HEEigenschaften des Algorithmusses von Ricard und Agrawala @HB a) @HPAnzahl der Nachrichten@HB, um einen gegenseitigen Ausschluß zu garantieren @HLN - 1 REQUEST's verschicken @HBan alle Kunden außer mir @HLN - 1 REPLY's erhalten @HBvon allen Kunden außer mir @HL───────────── Σ : 2 (N - 1) @HB Diese Zahl kann man bei anderen Voraussetzungen verringern, wie - der Algorithmus von @HPSuzuki/Kasami@HB (N Nachrichten) oder - der Algorithmus von @HPMeakawa@HB (c * √N Nachrichten) zeigen. @HBb) Der @HPgegenseitige Ausschluß@HB ist gesichert. Beweis durch Widerspruch: Annahme: Knoten A und B sind gleichzeitig im kritischen Gebiet. Dieser Zustand kann nur auf Grund folgender Situationen eingetreten sein: 1. Fall: Einer ist im kritischen Gebiet und der andere kommt hinzu. Zum Beispiel hat B als erster ein REQUEST geschickt und A will noch nicht ins kritische Gebiet, schickt also ein REPLY an B. @HAREQUEST REPLY @HLB @HP─────────> @HLA @HP─────────> @HLB@HB B betritt das kritische Gebiet. @HB A will nun auch ins kritische Gebiet, schickt also REQUEST an B. @HAREQUEST @HLA @HP─────────> @HLB@HB Da seq_nr (A) > seq_nr (B) (Bewerberzahl, die A bekannt ist, ist größer als die Bewerberzahl, die B bekannt ist) sendet B kein REPLY und somit kann A nicht gleichzeitig ins kritische Gebiet. ==> Widerspruch ! 2. Fall: A und B gelangen gleichzeitig ins kritische Gebiet. A und B müssen also gleichzeitig ein REQUEST schicken. Geht man davon aus, daß ihnen die gleiche Anzahl von Bewerbern bekannt ist, (seq_nr (A) = seq_nr (B)), so sind jedoch ihre Knoten- Nummern verschieden. Es schickt also nur einer ein REPLY zurück (und zwar der mit der größeren Knoten-Nummer). Folglich können nicht beide ins kritische Gebiet. ==> Widerspruch ! @HBc) Es kann kein @HPDeadlock@HB eintreten. Beweis durch Widerspruch: Annahme: Ein Deadlock sei eingetreten. Knoten A und B warten auf gegen- seitiges REPLY. Wenn A und B auf ein gegenseitiges REPLY warten, so heißt das, sie haben ihr REPLY an den anderen verzögert. Verzögern kann ein Knoten seine Einwilligung aber nur, wenn er Vorrang vor seinen Konkurren- ten hat (eine größere Priorität besitzt als sie). Wenn A und B aufeinander warten, so müßten sie die gleiche Priorität haben. Dies kann aber nicht sein, weil zumindest ihre Knoten-Nummern unterschiedlich sind und es wird der Knoten bevorzugt (genießt höhere Priorität), der die kleinere Knoten-Nummer hat. Der andere Knoten muß also sein REPLY senden. Einer erhält also betimmt ein REPLY. ==> Widerspruch ! @HBd) Es kann kein Knoten @HPverhungern@HB. Beweis durch Widerspruch: Annahme: Ein Knoten wird dauernd bei seiner Bewerbung um das kritische Gebiet übergangen. Wenn ein Knoten dauernd übergangen wird, so heißt das, daß er nie alle REPLY's der anderen Knoten erhält. Bewirbt sich ein Knoten A um das kritische Gebiet, so ist vor ihm eine endliche Zahl von Anforderungen. Die ihm bekannte Bewerberzahl seq_nr (A) liegt also zwischen 0 und (N-1). Bewirbt sich danach ein anderer Knoten B auch um das kritische Gebiet, so darf er seine Einwilligung (REPLY) nur verzögern, wenn die ihm bekannte Bewerber- zahl seq_nr (B) kleiner ist als die des Knotens A. Sie muß aber größer sein, da er von A bereits ein REQUEST erhalten hat mit dessen Bewerberzahl (seq_nr (A)) und dazu kommt noch die Bewerbung des Knotens A. Es gilt also seq_nr (B) = seq_nr (A) + 1 > seq_nr (A). @HB Die Bewerber vor A schicken ihm ihr REPLY, sobald sie das kritische Gebiet verlassen haben. Die Bewerber nach A müssen ihm ihr REPLY schicken, weil sie die größeren Bewerberzahlen haben. Der Knoten A hat also nach endlicher Zeit alle REPLY's erhalten. Es entsteht im Prinzip eine FIFO-⌐Warteschlange@BS1¬. e) @HPAusfall@HB eines Knotens Wenn ein Knoten ausfällt, so kann er kein REPLY mehr senden. Er würde somit das gesamte Netz lahmlegen. Man benutzt deshalb eine @HPtime-out-Zeit@HB. Verstreicht sie, ohne daß der Knoten alle REPLY's erhalten hat, so weiß er, daß der Knoten mit dem fehlenden REPLY ausgefallen ist. Er wertet dieses Ereignis aber so, als wenn er von dem ausgefallenen Knoten ein REPLY erhalten hätte und kann somit weiterarbeiten. Die Größe der time-out-Zeit ist ein Erfahrungs- wert, der sich an der Übertragungszeit von REQUEST und REPLY orientiert, eventuell unter Berücksichtigung von Verarbeitungszeiten. @HBf) Knoten @HPeinfügen / löschen@HB Es müssen alle anderen Knoten von einer Änderung (Knoten einfügen oder löschen) informiert werden. Man benötigt dafür einen eigenen Nachrich- tentyp. Wird ein neuer Knoten eingefügt, so nimmt er Kontakt zu irgendeinem Knoten im Netz auf. Dieser teilt dann den restlichen Knoten diese Neuigkeit mit. g) @HPTopologie@HB, die dem Algorithmus zu Grunde liegt Der Algorithmus ist, so wie er hier angegeben ist, für ein Netz ausge- legt, bei dem jeder Knoten mit jedem anderen verbunden ist. Er ist aber auch auf andere Topologien, wie zum Beispiel Ringform, anwendbar. Bei der Ringform kann man sich das REPLY als Nachricht sparen. Erreicht ein REQUEST seinen Absender, so wertet man dieses Ereignis als REPLY. @HBh) @HPPrioritätenvergabe@HB Bei dem hier vorgestellten Algorithmus werden kleine Knoten-Nummern bevorzugt, haben also eine höhere Priorität. Eine andere Möglichkeit, die Prioritäten festzulegen, ist folgende: Man erhöht beim Senden eines REQUEST die seq_nr nicht um 1, sondern um eine Zufallszahl, wobei - Prozesse hoher Priorität um eine kleine Zufallszahl und - Prozesse niedrigerer Priorität um eine größere Zufallszahl erhöht werden. weiter mit ⌐Nachrichtenwege@BS___6¬ AHBAA #!!# Nachrichtenwege @EH Bereitstellen von Nachrichtenwegen @HB Bei der Zusammenschaltung von physikalischen Übertragungskanälen zu Nach- richtenwegen im Rechnernetz werden im wesentlichen die folgenden Verfahren angewendet. Zur Anschauung dient dieses Beispiel-Teilnetz: @HK╔══════════════════════════════════════════╗ @HA┌────────┐ @HK║ @HA┌───┐ @HA┌───┐ @HA┌───┐ @HA┌───┐ @HK║ @HA┌──────┐ @HA│ @HLQuelle @HA│@HP─────>@HA│ @HLA @HA│@HP─────>@HA│ @HLB @HA│@HP─────>@HA│ @HLC @HA│@HP─────>@HA│ @HLD @HA│@HP─────>@HA│ @HLZiel @HA│ @HA└────────┘ @HK║ @HA└───┘ @HA└───┘ @HA└───┘ @HA└───┘ @HK║ @HA└──────┘ @HK╚══════════════════════════════════════════╝ @HEa) Circuit switching (Leitungsdurchschaltung) @HB Prinzip: Es wird der gesamte Nachrichtenweg von der Nachrichtenquelle bis zum Ziel aufgebaut. Dies geschieht durch eine spezielle Nachricht. Sie dient zur Beschlagnahmung der Kanäle, die zum Nachrichtenweg gehören, für die gesamte Dauer einer @HPSession@HB (Übertragungsgespräch). Nachdem der Weg aufgebaut ist, wird ein Signal an die Quelle zurückge- sendet, auf Grund dessen die Datenübertragung beginnt. Es können dabei mehrere Nachrichten übermittelt werden. Erst wenn die Quelle den Nachrichtenweg wieder freigibt, sind die Nachrichtenkanäle wieder frei für Nachrichten-Übertragungen zwischen anderen Netzknoten. @HAStart @HP─>@HL║A @HL║B @HL║C @HL║D @HA┐ @HL║@HP──────┐@HASignal @HL║ @HL║ @HL║ @HA│ K @HB= Verzögerung @HL║ @HP└──────>@HL║@HA┐K @HL║ @HL║ @HA│ @HBwegen Kanal- @HL║ ║@HA┘@HP─────┐ @HL║@HA┐Ü @HL║ @HA│ @HBbelegtheit @HL║ ║ @HP└──────>@HL║@HA┘ @HL║ @HA│ @HL║ ║ ║@HP──────┐ @HL║ @HA│ Ü @HB= Über- @HL║ ║ ║ @HP└──────>@HL║ @HA│ @HBtragungs- @HL║ ║ ║ @HP┌───────@HL║ @HA│ @HBverzögerung @HL║ @HAReturn-@HL║@HASignal@HP┌──────────────┘ @HL║ @HA│ @HL║ @HP┌──────────────┘ @HL║ ║ @HA├ Bedienzeit @HL║@HP<─────┘ @HL║ ║ ║ @HA│ @HA┌@NL║@NP──────┐@HL ║ ║ ║ @HA│ @HAI┤@NL║ @NP└──────────────┐@HL ║ ║ @HA│ I @HB= Datenüber- @HA│@NL║ @NL║ @NP└──────────────┐@HL ║ @HA│ @HBtragungszeit @HA└@NL║@NP──────┐ @NL║ @NADaten ──> @NL║ @NP└───────@NL║@HA │ @HL║ @NP└──────────────┐ @NL║ @NL║@HA │ @HL║ ║ @NP└──────────────┐ @NL║@HA │ @HL║ ║ ║ @NP└───────@NL║@HP─>@HA┘Ende @HEb) Message switching (Nachrichtenvermittlung) @HB Prinzip: Bei der Übertragung wird immer nur ein Kanal beschlagnahmt. Die Nach- richt wird zuerst von der Quelle zum nächsten Knoten innerhalb des Nachrichtenweges geschickt. Wenn die ganze Nachricht dort angekommen ist (Zwischenspeicherung), wird das nächste Wegstück ausgewählt. Ist der ausgewählte Kanal bereits belegt, wartet die Nachricht in einer Queue, bis er wieder frei ist. Die Nachricht hüpft also quasi von Knoten zu Knoten durch das Netz und wartet, wenn Kanäle belegt sind. Bei diesem Übertragungs-Verfahren wird die Nachricht in einen Header und die eigentlichen Daten unterteilt. Der @HPHeader@HB beinhaltet Infor- mationen über Ursprung, Ziel, Länge der Nachricht usw. Sonderzeichen kennzeichnen den Beginn und das Ende der Nachrichtenteile. @HAStart @HP─>@HL║A ║B ║C ║D @HA┐ @NL║@NP▀▀▀▀▀▀█@HL ║ ║ ║ @HA│ W @HB= Zeit für @NL║ @NP▀▀▀▀▀▀▀▀@NL║@HL ║ ║ @HA│ @HBWegermittlung @NL║ @NADaten ──>@NL ║@HL ║ ║ @HA│ @NL║@NP──────┐ @NL║@HL ║ ║ @HA│ @HL║ @NP└───────@NL║@HA┐W@HL ║ ║ @HA│ @HL║ ║@HA│ @HL║ ║ @HA│ @HL║ @NL║@NP▀▀▀▀▀▀█@HL ║ ║ @HA├ Bedienzeit @HL║ @NL║ @NP▀▀▀▀▀▀▀▀@NL║@HL ║ @HA│ @HL║ @NL║ @NADaten ──> @NL║@HL ║ @HA│ @HB(kürzer als bei @HL║ @NL║@NP──────┐ @NL║@HL ║ @HA│ @HBcircuit- @HL║ ║ @NP└───────@NL║@HL ║ @HA│ @HBswitching) @HL║ ║ @HL║ ║ @HA│ @HL║ ║ @NL║@NP▀▀▀▀▀▀█@HL ║ @HA│ @HL║ ║ @NL║ @NP▀▀▀▀▀▀▀▀@NL║@HL @HA│ @HL║ ║ @NL║ @NADaten ──> @NL║@HL @HA│ @HL║ ║ @NL║@NP──────┐ @NL║@HL @HA│ @HL║ ║ ║ @NP└───────@NL║@HP─>@HA┘Ende @HEc) Packet switching (Paket-Nachrichten-Vermittlung) @HB Prinzip: Die Nachricht wird im Prinzip wie beim message switching übertragen, aber mit dem Unterschied, daß die Nachrichten in Pakete mit maximaler Länge (Beispiel: Nachricht 3,5 kBit ==> 3 Pakete mit Länge 1 kBit und 1 Paket mit Länge ½ kBit) zerstückelt werden. Die Pakete werden dann nach dem message switching Verfahren verschickt. Dabei können mehrere Pakete der selben Nachricht gleichzeitig durch das Netz wandern, @HPpipeling-Effekt@HB. Die Übertragungsverzögerung verringert sich gegenüber message switching beträchtlich (proportional zu der Anzahl der Pakete, in die die Nach- richt zerstückelt wird). Jedes Nachrichtenpaket benötigt einen eigenen Header. @HAStart @HP─>@HL║A ║B ║C ║D @HA┐ @NL║@NP▀▀▀▀▀▀█@HL ║ ║ ║ @HA│ @NL║ @NADaten@NP▀▀▀▀▀▀▀▀@NL║@HL ║ ║ @HA│ @NL║@NP▀▀▀▀▀▀█ @NA──> @NL║@HL ║ ║ @HA│ @NL║ @NADaten@NP▀▀▀▀▀▀▀▀@NL║@NP▀▀▀▀▀▀█@HL ║ ║ @HA│ @NL║@NP▀▀▀▀▀▀█ @NA──> @NL║ @NP▀▀▀▀▀▀▀▀@NL║@HL ║ @HA├ Bedienzeit @NL║ @NADaten@NP▀▀▀▀▀▀▀▀@NL║@NP▀▀▀▀▀▀█ @NL║@HL ║ @HA│ @NL║@NP──────┐ @NA──> @NL║ @NP▀▀▀▀▀▀▀▀@NL║@NP▀▀▀▀▀▀█@HL ║ @HA│ @HB(kürzer als bei @HL║ @NP└───────@NL║@NP▀▀▀▀▀▀█ @NL║ @NP▀▀▀▀▀▀▀▀@NL║@HA │ @HBmessage @HL║ @NL║ @NP▀▀▀▀▀▀▀▀@NL║@NP▀▀▀▀▀▀█ @NL║@HA │ @HBswitching) @HL║ @NL║@NP──────┐ @NL║ @NP▀▀▀▀▀▀▀▀@NL║@HA │ @HL║ ║ @NP└───────@NL║@NP▀▀▀▀▀▀█ @NL║@HA │ @HL║ ║ @NL║ @NP▀▀▀▀▀▀▀▀@NL║@HA │ @HL║ ║ @NL║@NP──────┐ @NL║@HA │ @HL║ ║ ║ @NP└───────@NL║@HP─>@HA┘Ende @HL║ ║ ║ ║ @HL║ ║ ║ ║ @HL║ ║ ║ ║ @HEVergleich der 3 Übertragungsverfahren @HB - Bei circuit switching werden am wenigsten Bits übertragen, während beim packet switching am meisten (zusätzlich zu den Daten noch die Header) übertragen werden. - Wenn ein großer, gleichmäßiger Datenstrom übertragen werden soll, ist circuit switching am sinnvollsten. Sind die Datenmengen aber klein und vielzählig, wie es bei Rechnern üblich ist, so empfiehlt es sich packet switching anzuwenden. - Beim packet switching Verfahren reichen geringere Speicherkapazitäten aus als bei den beiden anderen Verfahren. - Beim packet switching können sich Pakete überholen, worauf beim Zielknoten geachtet werden muß. @HBDa packet switching die größten Vorteile hat, ist es auch am weitesten verbreitet. Deshalb wird im folgenden immer von packet switching Netzen ausgegangen. weiter mit ⌐Satelliten@BS___6¬ AHBAA #!!# Satelliten @EH Satellitenübertragung @HB Für sehr große Strecken, insbesondere transkontinentale Entfernungen, erweist sich die Übertragung mittels Satelliten als besonders bedeutsam, vor allem auf Grund der sehr hohen Übertragungskapazität. Moderne Satelliten mit verbesserter Technologie machen diese Art der Übertragung schon bei Entfernungen von einigen hundert Kilometern rentabel. @HEWesentliche Eigenschaften stationärer, erdnaher Satelliten @HB a) Sie kreisen in @HP36.000 km Höhe@HB geostationär um die Erde. b) Sie empfangen die Signale vom Boden, setzen sie in ein anderes Frequenzband um, verstärken es und senden es wieder aus. Sie können also gleichzeitig @HPsenden und empfangen@HB. @HB c) Bei der Satellitenübertragung tritt eine große @HPVerzögerung@HB (0,24 - 0,27 sec) der Signale auf. Dies ist bedingt durch die großen Entfernungen (Erde - Satellit - Erde = 70.000 km). @HL km Lichtgeschwindigkeit c = 300.000 ───── sec 70.000 ==> ───────── ≈ 0,24 300.000 @HB d) Signale werden mit einer hohen @HPTrägerfrequenz@HB (12 - 14 GHz, G = 1000.000.000) gesendet. @HEKollisionen @HB Bei der Satellitenübertragung sendet eine Station Daten zum Satelliten, von dort werden sie zur Erde reflektiert und können von allen Stationen im Schatten des Satelliten (einschließlich des Senders selbst) empfangen werden. Mittels Adressierung wählt jede Station ihre Nachricht aus. Man muß dabei beachten, daß alle Stationen auf einem einzigen gemeinsamen Frequenzband Nachrichten senden und auf einem anderen gemeinsamen Frequenzband Nachrichten empfangen. Dadurch entsteht auch das Hauptproblem bei der Satellitenübertragung: ⌐Kollision@BS2¬en. Werden zwei oder mehrere Nachrichten gleichzeitig übertragen, treten Kollisionen auf, die es unmöglich machen, die verschiedenen Nachrichten beim Empfang zu unterscheiden. Sie sind praktisch zerstört und werden daher von den Empfängern zurückgewiesen. Sie müssen also nochmals gesendet werden. Gerade bei einem hohen Nachrichtenaufkommen führen Kollisionen zu einem niedrigen Durchsatz. Ein wichtiges praktisches Problem besteht also darin, Kollisionen zu vermeiden. @HEPure ALOHA @HB Die einfachste Art, die Datenpakete zu senden, ist die, daß jede Station zu jeder beliebigen Zeit ohne Rücksicht auf die anderen Stationen zu senden beginnen kann. Wenn ein Sender nach der Übertragungsverzögerung von rund 0,25 sec seine eigene Nachricht ungestört hört, also eine positive Bestätigung der Übertragung hat, nimmt er an, daß die Übertragung erfolg- reich war. Im anderen Fall ist eine Kollision aufgetreten und das Daten- paket muß nochmals gesendet werden. Dabei sollte eine zufällige Zeitspanne gewartet werden, bis erneut gesendet wird, da sonst eine weitere Kollision vorprogrammiert ist. Ein entscheidendes Kriterium auch bei der Satellitenübertragung ist der Durchsatz, das heißt wieviel Nachrichten bzw. Datenpakete kommen pro Zeiteinheit korrekt an. @HBSei t die Übertragungszeit für ein Paket @HL Paketlänge (bit) @HBbei Vernachlässigung der @HL t = ──────────────────────────── @HL Kanalkapazität (bit / sec) @HBÜbertragungsverzögerung Eine Kollision tritt nur dann nicht auf, wenn während der Zeit t vor und nach Beginn der Übertragung keine Übertragung eines anderen Paketes begonnen wird. @HEKollisionen bei Pure ALOHA @NP┌────────────────┐@HB @NP│ Paket A │@HB @NP└────────────────┘@HA : : @NP┌─────────────@NA:@NP══╗@HA : @NP│ Paket B @NA:@NP ║@HA : @NP└─────────────@NA:@NP══╝@HA : : │ : : @HBKollision@HA──@NP╔══@NA:@NP─────────────┐@HA : @NP║ @NA: @NPPaket C │@HA : @NP╚══@NA:@NP─────────────┘@HA : : @HP──┬────────────────┬────────────────┬──────────────────────────── @HA -t 0 +t @HO «─────────────────────────────────» @HB 2*t = gefährdetes Zeitintervall @HBUnter der Annahme einer Poissonverteilung für die Zahl der zu übertragen- den Datenpakete pro Zeiteinheit t gilt für die Wahrscheinlichkeit, daß während des gefährdeten Zeitintervalls der Länge 2t keine weitere Über- tragung beginnt:@HL -∩ * 2t p = e = p [keine Kollision] @HB Der Durchsatz D läßt sich nun aus dem gesamten Verkehrsaufkommen ∩ * t und der Wahrscheinlichkeit, daß keine Kollision auftritt, berechnen:@HL -∩ * 2t D = ∩ * t * p = ∩ * t * e @HBMaximaler Durchsatz bei Pure ALOHA:@HL dD -∩ * 2t -∩ * 2t D' = ──────── = 1 * e + ∩ * t (e - 2) d (∩t) -∩ * 2t = e (1 - ∩ * 2t)@HB Ableitung gleich Null setzen:@HL -∩ * 2t e (1 - ∩ * 2t) = 0 1 - ∩ * 2t = 0 ∩ * 2t = 1 -½ * 2 -1 ∩ * t = ½ ==> Dmax = ½ e = ½ e ≈ 0,184 ==> @HPDmax ≈ 18 %@HB @HBIm pure ALOHA System ist also eine maximale Auslastung von 18 % möglich, ein äußerst schlechter Wert, der in der Praxis nicht einmal genau erreicht werden kann, da nicht berücksichtigt wurde, daß auch die Wiederholungen wieder kollidieren können. Erhöht sich das Verkehrsaufkommen weiter, nehmen die Kollisionen derart zu, daß die meisten der Datenpakete nur noch Wiederholungen auf Grund vorhergehender Kollisionen sind, was rasch zum Zusammenbruch des gesamten Systems führt. @HESlotted ALOHA @HB Eine Verbesserung des Systems kann dadurch erreicht werden, daß ein @HPSynchronisierungstakt@HB mit dem Intervall t bei allen Stationen bewirkt, daß das System nicht zu einem beliebigen Zeitpunkt, sondern nur zum Zeitpunkt des Taktsignals beginnen darf. @HBWenn eine Station ein Datenpaket senden will, muß sie seine Übertragung beim Slotted ALOHA also solange verzögern, bis das Taktsignal kommt. Das gefährdete Zeitintervall, in dem ein Paket gestört werden kann, beträgt jetzt nicht mehr 2t, sondern nur noch t. Kollisionen treten nämlich nur dann auf, wenn mehrere Stationen zum selben Takt senden. Für die Wahrscheinlichkeit p [keine Kollision] ergibt sich nun:@HL -∩ * t p = e @HB und damit für den Durchsatz@HL -∩ * t D = ∩ * t * e @HBMaximaler Durchsatz beim Slotted ALOHA:@HL dD -∩ * t -∩ * t D' = ──────── = e + ∩ * t * (e - 1) d (∩t) -∩ * t e * (1 - ∩ * t) = 0 1 - ∩ * t = 0 -1 ∩ * t = 1 ==> Dmax = 1 * e ≈ 0,368 ==> @HPDmax ≈ 36,8 %@HB @HAD @HP/│\ @HA1,0 @HP┤ @HBDer maximale Durchsatz ist also beim Slotted ALOHA @HP│ @HBdoppelt so groß, wie beim Pur Aloha System. Aber auch @HP│ @HBdieser Wert ist nur ein theoretisches Maximum, das auf @HA0,8 @HP┤ @HBGrund von Kollisionen der Wiederholungspakete nicht @HP│ @HBganz erreicht werden kann. @HP│ @HA0,6 @HP┤ @HP│ @HP│ @HA0,4 @HP┤@HA...........................@HO* @HP│ @HO* @HA: @HO* @HO* @HB: Slotted ALOHA @HP│ @HO* @HA: @HO* @HLo @HB: Pure ALOHA @HA0,2 @HP┤@HA...................@HO*@HA..@HLo @HA: @HO* @HP│ @HO* @HLo @HA: @HLo@HA: @HO* @HP│ @HO* @HLo @HA: @HA: @HLo @HO* @HA∩ * t @HP├@HO*@HLo@HP───────────┬────────┬────┬───────────@HLo@HP─┬@HO*@HP────────────┬──> @HA0,01 0,1 0,5 1 10 100 100 @HB weiter mit ⌐Rundfunknetze@BS___6¬ AHBAA #!!# Rundfunknetze Bei der Rundfunkübertragung können die vom Sender ausgesandten Signale innerhalb der Reichweite des Senders von jedem Empfangssystem aufgenommen werden. Eine Nachricht wird daher nicht nur von dem Empfänger, für den sie bestimmt ist, empfangen, sondern prinzipiell von allen teilnehmenden Stationen. Auf Grund der in der Nachricht mitgeführten Adresse der Nach- richt nehmen die Empfangsstationen eine Nachricht entweder an oder igno- rieren sie. @HECSMA (carrier sense multiple access) @HB In Rundfunknetzen werden Kollisionen weitgehend durch ein "in den Kanal hineinhorchen" vermieden, bevor ein Datenpaket gesendet wird. Da jede Station den gesamten Datenverkehr mithören kann, ist es möglich, festzu- stellen, ob der Übertragungskanal frei ist oder nicht. Ist er frei, kann das Paket gesendet werden, sonst wird wird es zurückgehalten, um eine Kollisation zu vermeiden. Zu einem späteren Zeitpunkt wird dann ein neuer Versuch unternommen. Dieses System wird CSMA (carrier sense multiple access, "Bote Verstand mehrfach Zugang") genannt. (siehe ⌐CSMA-Netz@BS2¬) @HEKollisionen bei CSMA @HBNatürlich können auch @HBbeim CSMA-System @HP│@NP┌────────────────┐@HA Station 1 @HBKollisionen entstehen. @HAStation 1 @HP│@NP│ Paket A │@HA sendet @HBZu einer Kollision @HP│@NP└────────────────┘@HA Paket A @HBkommt es, wenn zwei @HP│ @HA\ \ @HBStationen gleichzeitig @HP│ @HA\ \ @HBoder in einem Zeitab- @HP│ @HA\ \ @HBstand, der kürzer ist @HP│ @NP┌────────────────┐@HA Station 2 @HBals die Übertragungs- @HP│ @NP│ Paket A │@HA kann Paket A @HBzeit des ersten @HP│ @NP└────────────────┘@HA empfangen @HBSignals, auf der @HP│ @HA: @HBLeitung zu senden @HP│ @NP┌──@NA:@NP─────────────┐@HA Station 2 @HBbeginen. @HAStation 2 @HP│ @NP│ @NA: @NPPaket B │@HA sendet @HBStation 2 beginnt zu @HP│ @NP└──@NA:@NP─────────────┘@HA Paket B @HBsenden, weil es das @HP│ @HA: @HBSignal der Station 1 @HP└────────┬──────────────────────────── @HBnoch nicht empfangen @HO«────d───» @HBhat. ==> Kollision @HBBeim CSMA Verfahren sind Übertragungsraten von 1 Mbit / sec und Distanzen von mehreren hundert Metern typische Werte. Das Verfahren wird häufig in ⌐Ethernetz@BS___6¬en angewandt. @HEZugriffsprotokolle beim CSMA @HB siehe auch ⌐CSMA-Protokoll@BS2¬ a) @HPNonpersistent CSMA-Protokoll@HB (nonpersistent = nicht ständig) Eine sendewillige Station beginnt zu senden, wenn sie den Übertragungs- kanal frei vorfindet. Ist er jedoch durch eine bereits stattfindende Übertragung belegt, so wartet die Station nicht durch andauerndes (nonpersistent) Mithören, bis der Übertragungskanal frei ist, sondern wiederholt ihren Sendeversuch wie im Kollisionsfall zu einem späteren, zufällig gewählten Zeitpunkt. @HBb) @HP1-persistent CSMA-Protokoll@HB (persistent = ständig) Eine sendewillige Station beginnt sofort (das heißt mit der Wahrschein- lichkeit 1) zu senden, wenn der Übertragungskanal frei ist oder, falls er durch eine gerade stattfindende Übertragung belegt ist, unmittelbar nach dessen Freigabe. Hat dabei mehr als eine Station auf das Ende einer laufenden Übertragung gewartet, so ergibt sich unweigerlich (mit der Wahrscheinlichkeit 1) eine Kollision. Nach einer Kollision wartet die Sendestation eine unbestimmte Zeit bis zu einem erneuten Sendeversuch. c) @HPp-persistent CSMA-Protokoll@HB (nur auf Slotted Channels) Wenn der Übertragungskanal frei ist, beginnt eine sendewillige Station mit der Wahrscheinlichkeit p zu senden. Mit der Wahrscheinlichkeit q = 1 - p wird das Absenden um die Zeit Signalverzögerung Station - Station d = ───────────────────────────────────── Übertragungszeit für ein Paket verzögert. Ist nach dieser Verzögerung der Übertragungskanal noch frei, so sendet die Station wieder mit der Wahrscheinlichkeit q = 1 - p. Dieser Vorgang wiederholt sich so lange, bis das Datenpaket übertragen ist oder eine andere Station zu senden begonnen hat. Ist der Übertragungskanal belegt, so wird weiter in den Kanal gehorcht, bis die vorhergehende Übertragung beendet ist. Anschließend sendet die Station, die gewartet hat mit der Wahrscheinlichkeit p und verzögert mit der Wahrscheinlichkeit q = 1 - p. @HBd) @HPCSMA / CD-Protokoll@HB (CSMA mit Collision-Detection) Jede Station, die sendet, kann feststellen, ob eine Kollision statt- findet. Es wird dabei eine minimale Paketlänge vorgegeben, die so groß gewählt wird, daß der Sender auch im ungünstigsten Fall beim Erkennen einer Kollision noch immer das gleiche Paket sendet. Wird eine Kolli- sion festgestellt, so kann die Übertragung des Datenpaketes sofort abgebrochen werden, weil es sowieso noch einmal übertragen werden muß. Mit dieser Maßnahme wird die Zeitdauer, mit der der Übertragungskanal durch Kollision nutzlos belegt ist, reduziert. @HAD @HP/│\ @HEDurchsatzvergleich der verschiedenen Zugriffsprotokolle @HA1,0 @HP┤ @HP│ @HLo @HB: pure ALOHA @HP│ @HO* @HB: slotted ALOHA @HN° @HA0,8 @HP┤ @HM+ @HB: 1-persistent CSMA @HN° @HK# @HN° @HP│ @HJx @HB: 0,1 persistent CSMA @HJx @HN° @HK# @HK# @HN° @HP│ @HK# @HB: nonpersistent CSMA @HJx @HN°@HK# @HJx @HK# @HN° @HA0,6 @HP┤ @HN° @HB: slotted nonpersistent @HJx @HN°@HK# @HJx @HK# @HN° @HP│ @HBCSMA @HJx @HM+ @HK#@HN° @HJx @HK# @HN° @HP│ @HJx@HM+ @HK#@HN° @HM+ @HJx @HK# @HN° @HA0,4 @HP┤ @HJx@HM+ @HK#@HN°@HO* @HM+ @HP│ @HJx@HM+@HK#@HN°@HO* @HO* @HM+ @HP│ @HJx@HM+ @HK#@HN°@HO* @HO* @HM+ @HA0,2 @HP┤ @HJx@HM+ @HK#@HN°@HO* @HLo @HO* @HM+ @HP│ @HK#@HN°@HJx@HM+ @HO* @HLo @HLo @HO* @HM+ @HP│ @HJx@HM+@HO*@HLo @HLo @HO* @HM+ @HA∩ * t @HP├@HO*@HLo@HK#@HP──────────┬────────┬────┬───────────@HLo@HP─┬@HO*@HP─@HM+@HP──────────┬──> @HA0,01 0,1 0,5 1 10 100 100 @HBFazit: Mit CSMA-Protokollen läßt sich ein größerer Durchsatz erzielen als mit den ALOHA-Protokollen. Bei CSMA-Protokollen läßt sich der größte Durchsatz mit dem nonpersistent-CSMA bzw. slotted nonpersistent CSMA-Protokoll erreichen. weiter mit ⌐ARPA-Netz@BS___6¬ AHBAA #!!# ARPA-Netz Als Beispiel eines Netzes mit Paketvermittlung sei hier das @HPARPA-Netz@HB (Advanced Research Project Agency) angeführt. 1967 wurde damit begonnen, es aufzubauen. Zu Beginn bestand es im wesentlichen aus zwei Teilen: - einer gewissen Anzahl von verschiedenen Datenverarbeitungsanlagen, @HPHost@HB genannt (Wirtrechner) - einem @HPKnotennetz@HB bestehend aus paketübertragenden Netzknotenrechnern (IMP's = Interface Message Processors), die über 50 kBit/sec Leitungen miteinander verbunden sind. Jeder Wirtrechner (Host) ist direkt an ein IMP angeschlossen. In der Zwischenzeit besteht das Netz aus weit mehr als 100 Netzknoten- rechnern, die über die ganze USA verteilt sind. Über Satellit sind auch Hawaii und Europa in das Netz integriert. (Bei der Satellitenübertragung beträgt die Kanalkapazität 7,2 kBit / sec, ALOHA-Protokoll). @HBDie Übertragung von Nachrichten wird von einer Hierarchie von Protokollen gesteuert. Mittels dieser Protokolle werden Nachrichten zuerst vom Wirt- rechner zum zugehörigen IMP übertragen. Dort wird jede Nachricht in Pakete mit einer Höchstlänge von 1000 Bit unterteilt. Mit einer Zieladresse versehen, wird nun jedes Paket auf Grund eines Routing-Algorithmusses, der den schnellsten Weg zum Ziel-IMP errechnet, von IMP zu IMP weiterge- geben, bis der Zielknoten erreicht ist. Wenn alle Pakete einer Nachricht korrekt am Ziel-IMP angekommen sind, wird die gesamte Nachricht dem Ziel- Wirtrechner übergeben. weiter mit ⌐Ethernet@BS___6¬ AHBAA #!!# Ethernet Das ⌐Ethernet@BS2¬ ist ein @HPlokales ⌐Bus@BS2¬-Netz@HB, bei dem ein Koaxialkabel als Über- tragungskanal verwendet wird. Es wurde Anfang der 70er Jahre entwickelt. Die Anzapfung erfolgt mit einem kleinen mechanischen Gerät. Dabei wird eine Nadel in das Koaxial-Kabel eingestoßen und genau bis auf den Leiter abgesenkt. Das Kabel braucht also nicht aufgeschnitten zu werden. @HBDie @HPÜbertragungsrate@HB auf dem Koaxialkabel beträgt etwa 10 MBit / sec. Beim Zugriff auf den Kanal wird ein CSMA-Protokoll verwendet. Die Knotenzahl beim Ethernetz ist auf 1024 beschränkt. Zwei Knoten dürfen nicht mehr als 500 Meter auseinanderliegen und die gesamte Leitungslänge darf maximal 2500 Meter betragen. ??? weiter mit ⌐Token-Ring@BS___6¬ AHBAA #!!# Token-Ring Ein @HPToken-Ring@HB ist ein @HPlokales Netz mit ringförmiger Topologie@HB. Die Stationen sind über einen Übertragungskanal seriell miteinander verbunden. Seriell heißt, daß die Information Bit für Bit von einer Station zur nächsten übertragen wird. Die Sendeerlaubnis auf den Kanal wird mittels einer Berechtigungsmarke, dem @HPToken@HB, vergeben. Ein Token ist ein bestimmtes Bitmuster (z.B. 0xFF), das auf dem Ring kreist. Sobald die Station, die zu einem bestimmten Zeit- punkt das Token an sich genommen hat, ihre Übertragung beendet hat, sendet sie die Frei-Marke (die 1. Art von Token), die von der nächsten Station als Sendeerlaubnis interpretiert wird. Hat diese Station kein Sendebe- dürfnis, läßt sie die Frei-Marke zur übernächsten Station passieren, usw. Will sie aber ein Datenpaket senden, so wird die Frei-Marke in eine Belegt-Marke (die 2. Art von Token) umgewandelt, die Nachricht angehängt und gesendet. Der Empfänger erkennt an der Adresse im Header, daß ein Paket für ihn bestimmt ist. Er kopiert es in seinen Puffer und setzt im Original eventuell ein Quittierungs-Bit. @HBNach einem vollständigen Umlauf im Ring erreicht das Paket wieder den Sender, der die Nachricht aus dem Ring nimmt. Bei einer fairen Verplanung wandelt die Station die Marke wieder in eine Frei-Marke um, auch wenn sie noch weitere Pakete senden möchte. Es gibt aber auch die Strategie, daß eine Station soviel Pakete sendet, wie ihr im Augenblick zur Verfügung stehen. Um ein Token erkennen zu können, ist es notwendig, daß in jeder Station das ganze Bitmuster zwischengespeichert wird. Das bedingt, daß zum Bei- spiel bei einem Token der Länge 8 Bit in jeder Station eine Verzögerung von 8 Bit stattfindet (serielle Übertragung). Man kann aber durch geschickte Wahl der Übertragungsprozedur die Verzöger- ung auf nur 1 Bit reduzieren. Dazu wird ein Zähler benutzt. Die Frei-Marke möge zum Beispiel dem Bitmuster 1111 1111 (=0xFF) entsprechen. Empfängt eine Station das 1. Bit, so wird der Zähler bei einer 1 um eins erhöht (bei einer 0 wird der Zähler auf Null gesetzt) und das Bit an die nächste Station weitergeschickt. Ebenso wird mit dem nächsten Bit verfahren. @HEToken-Ring: Repeater unter der Lupe: @HM┌───@HP│@HM───────────────┐ @HE╔═══╗@HBRechner @HM│ @HP\│/ @HA■@HP────────> @HE║ ║ @HM│ @HA┌───┐ ┌────────┐ @HM│ @HE╚═╤═╝ @HM│ @HA│ @HBR @HA├──┤ @HBZähler @HA│ @HM│ @HBRechner @HM┌─┴─┐@HBRepeater @HM│ @HA└───┘ └────────┘ @HM│ @HP┌───@HM┤ ├@HP───┐ @HM│ @HP│ @HA■@HP<──────── @HP│ @HM└───┘ @HP│ @HM└───@HP│@HM───────────────┘ @HE╔═══╗ @HM┌─┴─┐ ┌─┴─┐ @HE╔═══╗ @HP\│/ @HBR = 1 Bit-Register @HE║ ╟─@HM┤ │ │ ├@HE─╢ ║ @HP: @HE╚═══╝ @HM└─┬─┘ └─┬─┘ @HE╚═══╝ @HM┌───@HP│@HM───────────────┐ @HP│ @HM┌───┐ @HP│ @HM│ @HP└────────>@HA■@HP────────> @HP└───@HM┤ ├@HP───┘ @HM│ @HA┌───┐ ┌────────┐ @HM│ @HM└─┬─┘ @HBsendewillige @HM│ @HA│ @HBR @HA├──┤ @HBZähler @HA│ @HM│ @HBRechner @HE╔═╧═╗ @HBStation hat @HM│ @HA└───┘ └────────┘ @HM│ @HE║ ║ @HBFreimarke ───@HM│ @HP┌<────────@HA■@HP<──────── @HE╚═══╝ @HBerkannt @HM└───@HP│@HM───────────────┘ @HBWenn das 8. Bit auch eine 1 ist (der Zähler hat schon 7 Einsen gezählt), dann wird dieses Bit verändert (auf 0 gesetzt), falls die Station ein Datenpaket senden will. Das neue Bitmuster (1111 1110) entspricht der Belegt-Marke. Will die Station nicht senden, dann wird auch das 8. Bit unverändert weitergegeben. Nach dem 8. Bit muß der Zähler auf jeden Fall wieder auf Null gesetzt werden. @HPVorteil beim Token Ring:@HB - Es können keine Kollisionen auftreten, da nur derjenige senden darf, der die Frei-Marke in die Belegt-Marke umgewandelt hat. @HPNachteile beim Token Ring:@HB - Man muß jeweils mit dem Senden warten, bis man im Besitz des Tokens ist. - Alle Repeater sind ständig beschäftigt. @HPProbleme beim Token-Ring:@HB - Wie kommt das erste Token ins Netz ? - Wer repariert ein defektes Token (zerstört, dupliziert, wird nicht mehr auf frei gesetzt) ? - Was geschieht beim Ausfall einer Station ? @HPProblemlösungen:@HB - Unter allen Repeatern ist einer ausgezeichnet, der etwas mehr darf und kann als die anderen. Er wird mit @HPaktiver Monitor@HB bezeichnet. Dieser setzt das erste Token ins Netz, erkennt, wenn ein Token zer- stört, dupliziert oder nicht mehr auf Frei gesetzt wird. Er ersetzt, z. B. nach einer time-out-Zeit (Übertragungszeit + Verzögerung), das defekte Token durch ein neues. @HB - Beim Ausfall eines aktiven Monitors wird durch einen Algorithmus einer der passiven Monitore zum neuen aktiven Monitor bestimmt. - Damit beim Ausfall einer Station trotzdem Nachrichten im Ring kreisen können, müssen ausgefallene Stationen umgangen werden. Dazu gibt es verschiedene Methoden, zum Beispiel indem von jeder Station eine Leitung zur übernächsten Station existiert. Oder es gibt einen zweiten Ring, in dem die Nachrichten in entgegengesetzter Richtung kreisen. @HEBit-Stuffing @HB Das Problem, daß das Bitmuster des Tokens in der Nachricht (im Header oder im Datenpaket) selbst vorkommt, wird durch Bit-Stuffing gelöst. Dadurch wird verhindert, daß die Bitfolge des Tokens, falls sie in der Nachricht auftritt, als Token interpretiert wird. @HPBeispiel für Bit-Stuffing:@HB Das Bitmuster eines Tokens sei 1111. Besteht eine Bitfolge in einer Nachricht aus vier aufeinander folgenden Einsen, so wird vom Sender nach der dritten 1 eine 0 in die Übertragung eingefügt. Der Empfänger entfernt aus der Nachrichtenfolge eine 0, wenn er drei aufeinander folgende 1en gelesen hat. @HO0 0 @HASender : @HF0 1 1 1 1 0 1 0 0 1 1 1 0 0 1 @HAKanal : @HF0 1 1 1 @HO0 @HF1 0 1 0 0 1 1 1 @HO0 @HF0 0 1 @HAEmpfänger : @HF0 1 1 1 / 1 0 1 0 0 1 1 1 / 0 0 1 @HB└────┬────┘ kein Token @HEToken-Ring Umlaufzeiten @HB @HPz @HB= Signallaufzeit (≈ 5 µsec/km ==> Geschwindigkeit ≈ 200.000 km/sec) @HPd @HB= Länge des Rings @HPN @HB= Anzahl der Ringstationen @HPL @HB= Latenz (Verzögerung) in Bits @HPv @HB= Bandbreite (Übertragungsrate) in Bit/sec @HPRingumlaufzeit U @HBDie Zeit, die ein Bit für @HL N * L @HBeinen kompletten Umlauf @HLU = z * d + ─────── @HBbenötigt. @HL v @HASignalumlaufzeit + N * (Verzögerungszeit pro Station) @HPRingbitzahl R @HBDie Anzahl Bits, die sich zu @HLR = U * v @HBjedem Zeitpunkt einer @HBÜbertragung im Netz befinden. @HARingumlaufzeit * Übertragungsrate @HBBeispiel: @HA 6 v = 10 Bit/sec, d = 2 km, N = 50 ==> R = 60 Bit 7 v = 10 Bit/sec, d = 2 km, N = 50 ==> R = 150 Bit @HBweiter mit ⌐slotted Ring@BS___6¬ AHBAA #!!# slotted Ring Slotted Rings (Cambridge Rings) sind spezielle @HPgetaktete Ring-Netze@HB. Bei ihnen sorgt der aktive Monitor (siehe ⌐Token-Ring@BS___6¬) dafür, daß auf dem Ring immer eine bestimmte feste Anzahl von "Behältern" zirkulieren, die zur Aufnahme von Datenpaketen dienen. Die Datenpakete sind dabei immer sehr kurz. @HA├────────────────────────Datenpaket (37 Bit)─────────────────────────┤ 8 Bit 8 Bit 16 Bit @HP..┬┬┬┬───────────────┬───────────────┬───────────────────────────────┬┬┬.. ││││ @HBAbsender-Adr. @HP│ @HBEmpfänger-Adr.@HP│ @HBDaten @HP│││ ..┴┴┴┴───────────────┴───────────────┴───────────────────────────────┴┴┴.. @HA └┬─┘ └┬┘ Kontrollbits Kontrollbits @HBDie Kontrollbits geben unter anderem Auskunft darüber, ob: - der Empfänger existiert oder nicht, - wenn er existiert, ob er das Paket angenommen hat oder nicht, - der Behälter leer ist oder nicht. Eine Station, die ein Datenpaket senden will, wartet bis ein leerer Behälter vorbeikommt und belegt ihn dann mit ihrem Datenpaket. Die empfangende Station läßt den Behälter als besetzt passieren und verwendet eines der letzten Bits des Datenpaketes zur Bestätigung des Empfangs. Die sendende Station wartet bis das Paket auf dem Ring wieder bei ihr vorbeikommt und gibt den Behälter wieder frei. Nun kann eine andere Station ihn wieder zur Übertragung eines Datenpaketes benützen. @HBweiter mit ⌐Wegewahl@BS___6¬ AHBAA #!!# Wegewahl Aus Gründen der Zuverlässigkeit ist es durchaus wünschenswert, daß ein Zielknoten auf verschiedenen Wegen erreicht werden kann. Dadurch entsteht allerdings das Problem der @HPWegewahl@HB. Die entscheidenden Kriterien für die Wahl eines Weges sind: - eine möglichst geringe Zeitverzögerung bei - größtmöglichem Durchsatz. Die meisten Methoden arbeiten tabellengesteuert (directory routing). Dabei wird in jedem Knoten eine @HPRouting-Tabelle@HB gespeichert, in der die günstigsten Wege zu allen Zielknoten eingetragen sind. In den Tabellen werden nicht die ganzen Wege gespeichert, sondern nur die Namen der jewei- ligen Nachbarknoten, über die diese Wege führen. Außerdem wird noch die Verzögerung für die ganzen Wege festgehalten. @HBZur Erstellung der Routing-Tabellen gibt es viele verschiedene Methoden. Grundsätzlich kann man zwei Gruppen unterscheiden: - die statische Wegewahl und - die dynamische (adoptive) Wegewahl. @HEStatische Wegewahl @HB Bei der statischen Wegewahl werden, vor Aufnahme des regulären Betriebes, sämtliche Tabellen erstellt und bleiben bestehen, unabhängig vom späteren Verkehrsaufkommen im Netz. Die Wege sind also statisch: Jedes Paket, das die selbe Zieladresse hat, wird auf dem selben Weg übertragen. @HPVorteile der statischen Wegewahl@HB - einfache Handhabung - relativ geringer Verwaltungsaufwand @HPNachteile der statischen Wegewahl@HB - Kann ohne äußere Eingriffe nicht auf eine veränderte Topologie (Ausfall von Verbindungsleitungen oder Netzknoten, Einfügen von neuen Netzknoten) reagieren, sich anpassen. - Kann ohne äußere Eingriffe nicht auf Verkehrssituationen im Netz (zum Beispiel lokale Überlastung) reagieren, sich anpassen. @HPMethoden der statischen Wegewahl@HB Es gibt zwei wesentliche Methoden: - die der kürzesten Wege, - die der minimal gewichteten Wege. @HEDynamische Wegewahl @HB Zum Unterschied zur statischen Wegewahl werden die Routing-Tabellen bei der dynamischen Wegewahl ständig dem sich ändernden Datenstrom angepaßt (adoptiert). In jedem Knoten werden Informationen über den momentanen Verkehr gesammelt, um damit lokal die Tabellen zu adoptieren. @HPVorteile der dynamischen Wegewahl@HB - kann sich dem Datenverkehr anpassen, ist also flexibel - kann sich ohne äußere Eingriffe einer veränderten Topologie anpassen - gute Nachrichten (z. B. ein ausgefallener Knoten ist wieder im Netz) sprechen sich schnell herum @HPNachteile der dynamischen Wegewahl@HB - höherer Aufwand als bei statischen Methoden - schlechte Nachrichten (z. B. daß ein Knoten ausgefallen ist) verbreiten sich sehr langsam - Ping-Pong-Effekt: Pakete werden zwischen Knoten hin und her geschoben bzw. sie durchlaufen Schleifen @HPMethoden der dynamischen Wegewahl@HB Es wird grob unterschieden zwischen - verteilten, - isolierten und - zentralisierten Methoden. @EH verteilte Methoden (= Informationsaustausch mit den Nachbarknoten) @HB @HEPUA (periodic update algorithm) @HB Beim PUA wird die Routing-Tabelle periodisch durch den Austausch von Informationen mit allen Nachbarknoten aktualisiert (updating). Dies ge- schieht alle 0,64 sec (rund 2 mal pro Sekunde). Jeder Nachbarknoten liefert also alle 0,64 sec @HBan Knoten n eine Spalte für dessen Ziel-Verzöge- @HE ╔═╧═╗ @HBrung-Tabelle. Sie gibt die augenblicklich beste @HE ─╢ @HB4@HE ╟─ @HBAbschätzung der Verzögerungen für die Strecken @HE ╚═╤═╝ @HBvon ihm zu allen Zielknoten an. Zu jedem Eintrag @HE ╔═╧═╗ ╔═╧═╗ ╔═══╗ @HBin die Tabelle addiert der Knoten n noch den @HE ─╢@HB17@HE ╟──╢ @HBn@HE ╟──╢ @HB8@HE ╟─ @HBWert q * const, wobei q die Länge der Kanal- @HE ╚═══╝ ╚═╤═╝ ╚═╤═╝ @HBschlange zu diesem Nachbarn ist und const eine @HE ╔═╧═╗ @HBKonstante, die der Verzögerung durch das Übertra-@HE ─╢ @HB7@HE ╟─ @HBgen an einen Nachbarn entspricht. @HE ╚═══╝ @HEZiel-Verzögerung-Tabelle von n Routing Tabelle von Knoten n @HB(wird nicht gespeichert) (wird gespeichert) @HAN a c h b a r k n o t e n @HAZiel- @HP│ @HP│@HAVerzö-@HP│ @HP│ @HA4 @HP│ @HA7 @HP│ @HA8 @HP│ @HA17 @HP│ @HAknoten@HP│ @HAüber @HP│@HAgerung@HP│ @HAZ @HP─────┼─────┼─────┼─────┼─────┤ ──────┼──────┼──────┤ @HAi @HA1 @HP│ @HJ8 @HP│ @HJ12 @HP│ @HJ9 @HP│ @HJ9 @HP│ @HA1 @HP│ @HJ4 @HP│ @HJ8 @HP│ @HAe @HA2 @HP│ @HJ17 @HP│ @HJ13 @HP│ @HJ9 @HP│ @HJ10 @HP│ @HA2 @HP│ @HJ8 @HP│ @HJ9 @HP│ @HAl @HA3 @HP│ @HJ18 @HP│ @HJ13 @HP│ @HJ24 @HP│ @HJ17 @HP│ @HB==> @HA3 @HP│ @HJ7 @HP│ @HJ13 @HP│ @HAk @HA: @HP│ @HP│ @HP│ @HP│ @HP│ @HA: @HP│ @HP│ @HP│ @HAn @HAk @HP│ @HJ11 @HP│ @HJ9 @HP│ @HJ15 @HP│ @HJ11 @HP│ @HAk @HP│ @HJ7 @HP│ @HJ9 @HP│ @HAo @HA: @HP│ @HP│ @HP│ @HP│ @HP│ @HA: @HP│ @HP│ @HP│ @HAt @HAN @HP│ @HJ16 @HP│ @HJ19 @HP│ @HJ14 @HP│ @HJ12 @HP│ @HAN @HP│ @HJ17 @HP│ @HJ12 @HP│ @HAe @HP│ │ │ │ │ │ │ │ @HAn @HB Knoten n wählt das Minimum aus jeder Zeile der Ziel-Verzögerung-Tabelle aus und trägt es in seine Routing Tabelle ein. @HBFällt ein Knoten aus, wird die Verzögerung für diesen Knoten mit ∞ (unendlich) angegeben. Den Ping-Pong-Effekt zwischen zwei benachbarten Knoten kann man verhindern, indem man verbietet, daß eine Nachricht an einen Knoten zurückgeschickt werden darf, von dem sie gerade kommt. @HEAUA (asynchronous update algorithm) @HB Bei diesem Algorithmus findet ein Tabellenaustausch asynchron statt, das heißt nur noch dann, wenn angenommen wird, daß es sich lohnt. Kriterium hierfür ist in den meisten Fällen das Überschreiten eines Schwellwertes der Verzögerung. PUA und AUA sind stabile Verfahren, das heißt Pakete kommen auch beim Ausfall von Knoten noch an. @HE Vergleich von PUA und AUA @HAVerzögerung @HP/│\ @HAin msec @HP│ @HO* @HB: PUA @HA200 @HP┤ @HLo @HB: AUA @HP│ @HO* @HK- @HB: Normalfall @HP│ @HO* * @HBohne Störung @HA150 @HP┤ @HO* * @HP│ @HLo o@HO*@HLo o o o o o o @HO* @HP│ @HLo @HO* @HLo @HO* @HA100 @HP┤ @HLo@HO* @HLo @HO* @HP│@HO*@HLo@HO*@HLo@HO* @HLo o o o@HO*@HLo@HO*@HLo@HO*@HLo@HO*@HLo@HO*@HLo@HO*@HLo@HO*@HLo@HO*@HLo@HO* @HP│@HK----------------------------------------------------- @HA50 @HP┤ @HP│ @HP│ @HP└────┬──────────────────┬────────────────────────────────> @HAT @HA Knoten Knoten kommt fällt aus wieder ins Netz @EH isolierte Methoden @HB Bei der isolierten Wegewahl legt sich jeder Knoten die Wege unabhängig von den anderen Knoten im Netz zurecht. @HESQ + BA (shortest queue + bias algorithm)@HB Wie gesagt, findet kein Informationsaustausch zwischen den Knoten statt. Die Entscheidung, welcher Knoten gewählt wird, wird auf Grund der Längen der Kanalschlangen zu den Nachbarknoten (= shortest queue) und dem kürzesten (entfernungsmäßig) Weg im Netz (= bias) getroffen. @HESQ + B + PUA (shortest queue + bias + periodic update algorithm)@HB Der Algorithmus ist deshalb isoliert, da der Informationsaustausch nur zum Updaten der kürzesten Wege dient. Durch den Ausfall von Kanälen oder auch Knoten, können sich die kürzesten Wege zu Zielknoten in ihrer Länge ändern. Um diesem Problem gerecht zu werden, erfolgt ein periodisches Updating dieser Information mit den Nachbarknoten. @EH zentralisierte Methode @HBBei einer zentralisierten Wegewahl werden in einem Routing-Kontrollzentrum periodisch die Beobachtungen und Messungen aus dem Netz gesammelt und für jedes Paar von Start- und Zielknoten der beste Weg errechnet. Diese Wege werden dann den einzelnen Knoten mitgeteilt. Die zentralisierte Wegewahl ist sehr fehleranfällig, insbesondere kann ein Ausfall des Kontrollzentrums katastrophale Folgen haben. @HBweiter mit ⌐Deadlock im Netz@BS___6¬ AHBAA #!!# Deadlock im Netz @HENachrichtenübermittlung @HB Die Nachrichtenübermittlung in Rechnernetzen erfolgt nach folgendem Prinzip: 1) Eine Nachricht wird im Nachrichtenpuffer gespeichert. 2) Es erfolgt eine Pufferanforderung im Zielknoten. 3) Wenn der Anforderung entsprochen wird, wird die Nachricht übertragen. (Wegen Übertragungsfehlern, z. B. Kollisionen aber beim Quellknoten noch nicht gelöscht.) 4) Wenn die Nachricht komplett und korrekt im Zielknoten angekommen ist, wird dies mit einem Signal quittiert. 5) Nach dem Empfang des Quittierungssignals im Quellknoten wird die Nachricht hier gelöscht. Gelangt eine Nachricht korrekt zum Zielknoten und wird dort aufgenommen, so wird sie gleichzeitig verbraucht, wodurch der Puffer wieder frei wird. @HEAuftreten von Deadlocks @HB Zum Thema Deadlock siehe auch: ⌐Deadlock@BS1¬ ⌐5 Philosophen@BS___3¬ ⌐Betriebsmittel II@BS___4¬ Deadlocks können in Rechnernetzen auftreten, auf Grund von a) falscher bzw. fehlerhafter Synchronisation b) Betriebsmittel-Knappheit im Knoten (zum Beispiel keine freien Puffer mehr im Knoten) c) Betriebsmittel-Knappheit im Netz (zum Beispiel keinen freien Puffer mehr im gesamten Netz) @HEBeispiel für Betriebsmittel-Knappheit im Knoten @HB @BO Knoten X Knoten Y @HB Zwei Nachrichten, A und B, @BP ┌────┬────┬────┐ ┌────┬────┬────┐ @HB bestehend aus den Paketen A1-A5 @BP │ @BMA3 @BP│ @BMB2 @BP│ │ │ @BMA5 @BP│ │ │ @HB bzw. B1-B4, seien für den Ziel- @BP ├────┼────┼────┤ ├────┼────┼────┤ @HB knoten Z bestimmt. Jedem Knoten @BP │ │ │ │ │ │ │ │ @HB stehen 6 Puffer zur Verfügung. @BP └────┴────┴────┘ └────┴────┴────┘ @HB @BP └─────┬─────┘ @HB Die vollständigen Nachrichten @BP \│/ @HB A und B können erst zusammenge- @BP ┌────┬────┬────┐ @HB setzt werden und damit auch ver- @BP │ @BMA1 @BP│ @BMB3 @BP│ @BMB1 @BP│ @HB braucht werden, wenn A3, A5 und @BP ├────┼────┼────┤@BOKnoten Z @HB B2 nach Z übertragen sind, jedoch @BP │ @BMA2 @BP│ @BMB4 @BP│ @BMA4 @BP│ @HB kann von Z überhaupt kein Knoten @BP └────┴────┴────┘ @HB mehr aufgenommen werden. Dazu @BP @HB müßte Z erst eine vollständig @BP @HB zusammengesetzte Nachricht @BP @HB verbrauchen. ==> @HPDeadlock @HEBeispiel für Betriebsmittel-Knappheit im Netz @BP ┌──────────────────┐ @HB Das Netz besteht aus den 3 @BP \│/ @BOX Y @BP│ @HB Knoten X, Y und Z. Jedem Knoten @BE ╔════════╗ ╔════@BP│@BE═══╗ @HB stehen 2 Puffer zur Verfügung. @BE ║ @BP┌────┐ @BE╟───────╢ @BP┌──┴─┐ @BE║ @HB @BE ║ @BP│ @BMA1 @BP├────────>@BE║ @BP│ @BMC @BP│ @BE║ @HB Knoten X hat eine Nachricht aus @BE ║ @BP├────┤ @BE║ ║ @BP├────┤ @BE║ @HB 2 Paketen für Knoten Y. Y hat @BE ║ @BP│ @BMA2 @BP├────────>@BE║ @BP│ @BMD @BP│ @BE║ @HB eine Nachricht für Knoten X und @BE ║ @BP└────┘ @BE║ ║ @BP└──┬─┘ @BE║ @HB eine für Z. Knoten Z hat je @BE ╚══════╤═╝ ╚═╤══@BP│@BE═══╝ @HB eine Nachricht für X und Y. @BP /│\ @BE│ │ @BP│ /│\ @HB @BP │ @BE│ @BOZ @BE│ @BP│ │ @HB Kein Knoten ist jedoch in der @BP │ @BE╔╧═══════════╧╗ @BP│ │ @HB Lage, eine Nachricht bzw. ein @BP │ @BE║ @BP┌────┬────┐ @BE║@BP<┘ │ @HB Paket zu übertragen, weil der @BP └───@BP┤ @BME @BP│ @BMF @BP├──────┘ @HB jeweilige Zielknoten keinen @BE ║ @BP└────┴────┘ @BE║ @HB freien Puffer für die Aufnahme @BE ╚═════════════╝ @HB hat. ==> @HPDeadlock @HBDa es nicht möglich ist, Rechnernetze so zu konstruieren, daß Deadlock- freiheit garantiert werden kann (Verhindern von Deadlocks ist nicht möglich), beschränkt man sich in Rechnernetzen auf das Erkennen und Beseitigen von Deadlocks und die Deadlock-Vermeidung. Zu beiden Verfahren geben wir einen Algorithmus an: a) Algorithmus zum Erkennen von Deadlocks in Rechnernetzen, von Ahuja 1979 b) Algorithmus zum Vermeiden von Deadlocks in Rechnernetzen von S. Taueg @HBweiter mit ⌐Ahuja@BS___6¬ siehe auch ⌐Deadlock-Vermeidung@BS___4¬ AHBAA #!!# Ahuja @EH Algorithmus zum Erkennen von Deadlocks (Ahuja 1979) @HB Der Algorithmus geht von dem Prinzip der Nachrichtenübertragung aus, das im Kapitel ⌐Deadlock im Netz@BS___6¬ besprochen wurde. Dazu kommen folgende Annahmen: - Jeder Puffer kann nur eine Nachricht aufnehmen. (Paketvermittlung ist nicht vorausgesetzt.) - Ein Puffer ist nicht entziehbar. - Die Aufnahme einer Nachricht im Zielknoten bedeutet gleichzeitig, daß die Nachricht verbraucht wird, wodurch der Puffer wieder frei wird. Bemerkungen: - Der Algorithmus ist @HPzentral@HB. - Voraussetzung ist, daß jeder Knoten mit jedem Knoten direkt verbunden ist (zumindestens mit jedem seiner Zielknoten). @HEIdee des Algorithmusses @HB In einer (n * n)-Matrix (n = Anzahl der Knoten im Netz) wird festgehalten, welcher Knoten an welchen Knoten Nachrichten verschicken will. Man tut nun so, als wenn man von den Knoten, deren Puffer alle belegt sind, Nachrichten an deren Zielknoten schickt, falls diese noch freie Puffer besitzen. Ist dies möglich (der jeweilige Zielknoten besitzt also noch freie Pufferplätze), so wird der Quellknoten in die Liste der Knoten mit freien Puffern aufgenommen. Dies wiederholt man für alle in der Matrix gespeicherten Knoten so lange, bis keine Nachrichten mehr an Zielknoten mit freien Puffern verschickt werden können. Bleibt am Ende ein Knoten übrig, dessen Puffer alle belegt waren und der keine Nachrichten verschicken konnte, dann und nur dann liegt ein Deadlock vor. @HEAlgorithmus @HPSchritt 1: @HAMatrix M (n * n) mit 0 initialisieren, Vektor V (n) mit 0 initialisieren @HPSchritt 2: @HAFür jeden Knoten Xi (1 ≤ i ≤ n) setze Vi = 1, wenn Knoten Xi mindestens einen freien Puffer hat Vi = 0, sonst. Enthält V weniger als zwei 0-Einträge, dann ist T' (der zu untersuchende Zustand des Netzes) kein Deadlockzustand. Enthält V nur 0-Einträge, dann ist T' ein Deadlockzustand. (Im gesamten Netz gibt es keinen freien Puffer mehr.) @HPSchritt 3: @HAFür jeden Knoten Xi setze Mij = 1, wenn eine Nachricht in Xi einen Puffer in Xj anfordert Mij = 0, sonst. @HPSchritt 4: a) @HAErzeuge eine Liste Y, die alle Indizes derjenigen Knoten Xi enthält, für die Vi = 1 ist. Gibt es keinen Knoten Xi, dann folgt Schritt 5. @HP b) @HAFür jede Zeile p mit Mpk = 1 (k = erstes Element von Y) und Vp = 0 setze Vp = 1 und nimm p in die Liste Y auf. @HP c) @HASetze k auf das nächste Element von Y und gehe wieder zu 4b. @HP d) @HAWiederhole diesen Schritt so lange, bis alle Einträge von Y überprüft sind. @HPSchritt 5: @HAÜberprüfe den Vektor V auf 0-Einträge. Gibt es mindestens ein Element j mit Vj = 0, dann und nur dann ist T' ein Deadlockzustand. @HBAufwand des Algorithmusses: @HPO (m + n²) @HBmit m = Anzahl Nachrichten in T' @HBBeispiel a) @HAXi p Xj Xi p Xj @HBb = 2 @HE╔═══╗@HP────>@HE╔═══╗ @HBT' = { (1, 1, 2), (1, 2, 4), @HP┌─>@HE║ @HO1 @HE║ @HE║ @HO2 @HE║@HP<─────┐ @HB (2, 1, 1), (2, 2, 4), @HP│ @HE╚═══╝@HP<────@HE╚═══╝ @HP│ @HB (3, 1, 2), (3, 2, 4), @HP│ /│\ │ │ │ @HB (4, 1, 1), (4, 2, 5), @HE╔═══╗ @HP│ │ └─────┐ │ @HE╔═══╗ @HB (5, 1, 1), (5, 2, 3) } @HE║ @HO6 @HE║ @HP│ │ │ │ @HE║ @HO3 @HE║ @HE╚═══╝ @HP│ └─────┐ │ │ @HE╚═══╝ @HP│ │ \│/ \│/ │ /│\ @HBXi = Quellknoten @HP│ @HE╔═══╗ @HP└───@HE╔═══╗ @HP│ │ @HBXj = Zielknoten @HP└──@HE║ @HO5 @HE║ ║ @HO4 @HE║@HP<───┘ │ @HBp = Pufferindex @HE╚═══╝@HP<────@HE╚═══╝ @HP│ @HBb = Pufferanzahl im Knoten @HP│ │ @HP└────────────────────┘ @HPSchritt 1: @HBM, V mit 0 initialisieren @HPSchritt 2: @HBV = (0, 0, 0, 0, 0, 1) @HPSchritt 3: @HB ┌ ┐ │ 0 1 0 1 0 0 │ │ 1 0 0 1 0 0 │ M = │ 0 1 0 1 0 0 │ │ 1 0 0 0 1 0 │ │ 1 0 1 0 0 0 │ │ 0 0 0 0 0 0 │ └ ┘ @HPSchritt 4: a) @HB Y = (6) @HP b) @HB - @HP c) @HB - @HP d) @HB - @HPSchritt 5: @HB T' ist Deadlock-Zustand @HBBeispiel b) @HA Xi p Xj Xi p Xj @HBb = 2 @HE╔═══╗ ╔═══╗ @HBT' = { (1, 1, 3), (1, 2, 5), @HP┌──@HE║ @HO1 @HE║@HP<────@HE║ @HO2 @HE║@HP──────┐ @HB (2, 1, 1), (2, 2, 3), @HP│ @HE╚═══╝ ╚═══╝ @HP│ @HB (3, 1, 4), (3, 2, 5), @HP│ │ /│\ \│/ @HB (4, 1, 2), (4, 2, 5) } @HP│ │ │ @HE╔═══╗ @HP│ └───────────│───>@HE║ @HO3 @HE║ @HP│ │ @HE╚═══╝ @HP│ │ │ │ @HBXi = Quellknoten @HP│ @HE╔═══╗ ╔═══╗ @HP│ │ @HBXj = Zielknoten @HP└─>@HE║ @HO5 @HE║@HP<────@HE║ @HO4 @HE║@HP<───┘ │ @HBp = Pufferindex @HE╚═══╝ ╚═══╝ @HP│ @HBb = Pufferanzahl im Knoten @HP/│\ │ └────────────────────┘ @HPSchritt 1: @HBM, V mit 0 initialisieren @HPSchritt 2: @HBV = (0, 0, 0, 0, 1) @HPSchritt 3: @HB ┌ ┐ │ 0 0 1 0 1 │ │ 1 0 1 0 0 │ M = │ 0 0 0 1 1 │ │ 0 1 0 0 1 │ │ 0 0 0 0 0 │ └ ┘ @HPSchritt 4: a) @HB Y = (5) @HP b) @HB k = 5 Zeilen p: p = {1, 3, 4} ==> V = (1, 0, 1, 1, 1) Y = (5, 1, 3, 4) @HP c) @HB k = 1 - k = 3 Zeilen p: p = {2} ==> V = (1, 1, 1, 1, 1) Y = (5, 1, 3, 4, 2) k = 4 - k = 2 - @HPSchritt 5: @HB T' ist deadlockfreier Zustand @HBweiter mit ⌐Taueg@BS___6¬ AHBAA #!!# Taueg @EH Algorithmus zum Vermeiden von Deadlocks (von S. Taueg) @HB Hinweise: - Der Algorithmus ist für ein Netzwerkmodell mit @HPPaketvermittlung@HB ausgelegt. - Es ist ein @HPverteilter Algorithmus@HB, das heißt jeder Knoten entscheidet nur auf Grund lokalen Wissens und unabhängig von anderen Knoten - Es gibt in jedem Knoten Kontroll-Prozeduren, die das Eintreten eines ⌐Deadlock@BS1¬s verhindern (@HPDeadlockfreiheit@HB garantieren). Annahmen: - Es gibt @HPfeste Wege@HB, die den Nachrichtenpaketen mitgegeben werden. - Der längste Weg eines Paketes sei @HPk@HB (nicht unbedingt der längste Weg im Netz). - In jedem Knoten gibt es @HPb@HB Puffer, wobei b > k ist. @HELokales Knotenwissen @HB - @HPf@HB : Anzahl freier Puffer - @HPg@HB : Anzahl der Pakete im Knoten - @HPq = (qo, ..., qk)@HB : Wobei qi die Anzahl der Pakete in einem Knoten angibt, dessen Entfernung vom Quellknoten i beträgt. 0 ≤ i ≤ k - @HPr = (ro, ..., rk)@HB : Wobei ri die Anzahl der Pakete in einem Knoten angibt, dessen Entfernung vom Zielknoten i beträgt. 0 ≤ i ≤ k Es gilt: @HPk k @HB1. @HPg = Σ qi = Σ ri @HB2.@HP f = b - g @HPi=0 i=0 @HEGlobaler Paketzustand @HB - @HPs@HB : Entfernung eines Paketes vom Quellknoten (source) - @HPd@HB : Entfernung eines Paketes vom Zielknoten (destination) Es gilt: @HPs + d ≤ k@HB └──┬──┘ Länge des Weges eines Paketes @HEKontrollprozeduren:@HB - @HP(f, d)@HB : Forward -Count-Controller; @HPFC@HB - @HP(r, d)@HB : Forward -State-Controller; @HPFS@HB - @HP(g, s)@HB : Backward-Count-Controller; @HPBC@HB - @HP(q, s)@HB : Backward-State-Controller; @HPBS@HB @HP(f, d) die FC-Kontroll-Prozedur@HB Die FC-Prozedur erlaubt die Generierung oder Übernahme eines Paketes, wenn die Anzahl der freien Puffer größer ist, als die Entfernung zum Zielknoten. @HL FC (f, d) = {(f, d) | d < f AND 0 ≤ d ≤ k AND 1 ≤ f ≤ b } @HB FC ist deadlockfrei. @HP(r, d) die FS-Kontroll-Prozedur@HB Die FS-Prozedur arbeitet in Anlehnung an die FC-Prozedur. Die FS-Prozedur betrachtet alle Pakete, geordnet nach der Entfernung zum jeweiligen Zielknoten. Sie erlaubt die Übernahme eines Paketes p, wenn für alle Pakete im Knoten, deren Entfernung i zum Zielknoten kleiner oder gleich der Ent- fernung d des Paketes p zu seinem Zielknoten ist, gilt, daß ihre jeweilige Entfernung i kleiner ist als die Anzahl der freien Puffer nach der Weitergabe der Pakete mit der Entfernung, die kleiner ist als i. @HL FS (r, d) = {(r, d) | für alle i mit 0 ≤ i ≤ gilt: k i < b - Σ rj AND 0 ≤ d ≤ k } j=i @HB FS ist deadlockfrei. @HP(g, s) die BC-Kontroll-Prozedur@HB Die BC-Prozedur erlaubt die Generierung oder Übernahme eines Paketes, wenn dieses Paket weiter vom Quellknoten entfernt ist, als die Differenz von k und der Anzahl der verbleibenden freien Puffer im Knoten. @HL BC (g, s) = {(g, s) | s ≥ g - b + (k + 1) AND 0 ≤ s ≤ k AND 0 ≤ g ≤ b - 1} @HB└──┬──┘ -f └───────┬───────┘ (k + 1) - f BC ist deadlockfrei. @HP(q, s) die BS-Kontroll-Prozedur@HB Die BS-Prozedur betrachtet alle Pakete, geordnet nach der Entfernung vom jeweiligen Zielknoten. Sie erlaubt die Übernahme eines Paketes p, wenn für alle Pakete im Knoten, deren Entfernung i vom Quellknoten größer oder gleich der Ent- fernung s des Paketes p von seinem Quellknoten ist, gilt, daß ihre jeweilige Entfernung i größer oder gleich ist als die Differenz von k und der Anzahl der freien Puffer nach der Weitergabe der Pakete mit der Entfernung, die größer ist als i. @HL BS (q, s) = {(q, s) | für alle i mit s ≤ i ≤ k gilt: i i ≥ (k + 1) - (b - Σ qj) AND 0 ≤ s ≤ k} j=0 @HB BS ist deadlockfrei. @HEBeweisidee für die Deadlockfreiheit der FC-Kontroll-Prozedur @HB Beweis durch Widerspruch Annahme: Deadlock sei eingetreten. Es können keine Pakete mehr verschickt werden. Sei p1 ein blockiertes Paket, daß sich im Knoten v1 befindet. v1 sei vom Zielknoten von p1 die Distanz d1 entfernt (d1 > 0, weil sonst v1 der Zielknoten von p1 wäre). Sei v2 der nächste Knoten auf dem Weg von p1 und sei f2 die Anzahl freierPuffer in v2. Es gilt dann: a) @HPd1 < b@HB , weil p1 sonst nicht von v1 aufgenommen worden wäre. b) @HP(d1 - 1) ≥ f2@HB, weil p1 sonst an v2 weitergegeben werden könnte. ==> @HPf2 < b@HB , das heißt v2 ist nicht leer, es gibt also wenigstens ein Paket in v2, das blockiert ist. Sei d2 die Entfernung des Paketes p2 mit der geringsten zurückgelegten Strecke zum Zielknoten in v2. Es gilt also: @HPd2 < f2 + 1@HB , weil p2 sonst nicht von v2 aufgenommen worden wäre Mit (d1 - 1) ≥ f2 ==> d1 ≥ f2 + 1 > d2 folgt dann @HPd2 < d1@HB ==> Im nächsten Knoten auf dem Weg von p1, dem Knoten v3, gibt es eben- falls ein blockiertes Paket p3 mit der Entfernung d3 und es gilt @HPd3 < d2@HB Usw., usf. Schließlich kommt man zu einem Knoten, der ein blockiertes Paket mit der Entfernung 0 besitzt. Es ist blockiert, obwohl es sich in seinem Zielknoten befindet. Das ist ein Widerspruch. ==> Die Annahme, es sei ein Deadlock eingetreten, ist falsch. @HEZahlenbeispiel @HB Da laut Annahme ein Deadlock vorliegt, müssen alle Pakete p1 bis p5 blockiert sein. @HAKnoten v1 Knoten v2 Knoten v3 Knoten v4 Knoten v5 @HE╔════════╗ ╔════════╗ ╔════════╗ ╔════════╗ ╔════════╗ @HE║ @HP┌────┐ @HE║ ║ @HP┌────┐ @HE║ ║ @HP┌────┐ @HE║ ║ @HP┌────┐ @HE║ ║ @HP┌────┐ @HE║ @HE║ @HP│ @HLp1 @HP│ @HE╟─────╢ @HP│ @HLp2 @HP│ @HE╟─────╢ @HP│ @HLp3 @HP│ @HE╟─────╢ @HP│ @HLp4 @HP│ @HE╟─────╢ @HP│ @HLp5 @HP│ @HE║ @HE║ @HP└────┘ @HE║ ║ @HP└────┘ @HE║ ║ @HP└────┘ @HE║ ║ @HP└────┘ @HE║ ║ @HP└────┘ @HE║ @HE║ @HAf1 @HE║ ║ @HAf2 @HE║ ║ @HAf3 @HE║ ║ @HAf4 @HE║ ║ @HAf5 @HE║ @HE╚════════╝ ╚════════╝ ╚════════╝ ╚════════╝ ╚════════╝ @HB d1 = 4 (Distanz von p1 zum Zielknoten v5) Es gilt: a) d1 = 4 < b b) (d1 - 1) ≥ f2 <==> 3 ≥ f2 @HBSei f2 = 3 < b ==> es existiert p2 (blockiert) Es gilt: d2 < f2 + 1 <==> d2 < 4 ==> d2 < d1 = 4 Es gilt: (d2 - 1) ≥ f3 <==> 2 ≥ f3 Sei f3 = 2 < b ==> es existiert p3 (blockiert) Es gilt: d3 < f3 + 1 <==> d3 < 3 ==> d3 < d2 = 3 Es gilt: (d3 - 1) ≥ f4 <==> 1 ≥ f4 Sei f4 = 1 < b ==> es existiert p4 (blockiert) Es gilt: d4 < f4 + 1 <==> d4 < 2 ==> d4 < d3 = 2 Es gilt: (d4 - 1) ≥ f5 <==> 0 ≥ f5 Sei f5 = 0 ==> es existiert p5 (blockiert) Es gilt: d5 < f5 + 1 <==> d5 < 1 ==> d5 < d4 = 1 <==> @HPd5 = 0@HB Widerspruch ! p5 wäre nicht blockiert. @HEBeispiel für die FC- und FS-Kontroll-Prozedur @HB @HPNetz mit@HB b = 7, k = 5, f = 7 (in diesem bestimmten Zustand) @HPEs kommen die Pakete:@HB P1 (d1=1), P2 (d2=2), P3 (d3=2), P4 (d4=4), P5 (d5=4), P6 (d6=5) @HPFC-Prozedur@HA f d @HB P1 : (7, 1) 1 < 7 ok ==> P1 angenommen; f = 6 P2 : (6, 2) 2 < 6 ok ==> P2 angenommen; f = 5 P3 : (5, 2) 2 < 5 ok ==> P3 angenommen; f = 4 P4 : (4, 4) 4 < 4 ko ==> P4 nicht angenommen; P5 : (4, 4) 4 < 4 ko ==> P5 nicht angenommen; P6 : (4, 5) 5 < 4 ko ==> P6 nicht angenommen; Bei umgekehrter Ankunftsreihenfolge der Pakete wären alle 6 Pakete angenommen worden. ==> Reihenfolge ist wichtig ! @HEFS-Prozedur @HA 0 1 2 3 4 5 = d@HB r = (0 0 0 0 0 0) P1 (d1=1) kommt ==> r = (0 1 0 0 0 0) 0 ≤ i ≤ 1 i = 0 0 < 7 - 1 = 6 i = 1 1 < 7 - 1 = 6 P1 angenommen P2 (d2=2) kommt ==> r = (0 1 1 0 0 0) 0 ≤ i ≤ 2 i = 0 0 < 7 - 2 = 5 i = 1 1 < 7 - 2 = 5 i = 2 2 < 7 - 1 = 6 P2 angenommen @HB P3 (d3=2) kommt ==> r = (0 1 2 0 0 0) 0 ≤ i ≤ 2 i = 0 0 < 7 - 3 = 4 i = 1 1 < 7 - 3 = 4 i = 2 2 < 7 - 2 = 5 P3 angenommen P4 (d4=4) kommt ==> r = (0 1 2 0 1 0) 0 ≤ i ≤ 4 i = 0 0 < 7 - 4 = 3 i = 1 1 < 7 - 4 = 3 i = 2 2 < 7 - 3 = 4 i = 3 3 > 7 - 1 = 6 i = 4 4 < 7 - 1 = 6 P4 angenommen @HB P5 (d5=4) kommt ==> r = (0 1 2 0 2 0) 0 ≤ i ≤ 4 i = 0 0 < 7 - 5 = 2 i = 1 1 < 7 - 5 = 2 i = 2 2 < 7 - 4 = 3 i = 3 3 > 7 - 2 = 5 i = 4 4 < 7 - 2 = 5 P5 angenommen P6 (d6=5) kommt ==> r = (0 1 2 0 2 1) 0 ≤ i ≤ 5 i = 0 0 < 7 - 6 = 1 i = 1 1 < 7 - 6 = 1 ko i = 2 2 < 7 - 5 = 2 ko i = 3 3 > 7 - 3 = 4 i = 4 4 < 7 - 3 = 4 ko i = 5 5 < 7 - 1 = 6 P6 nicht angenommen @HPBemerkungen@HB - Bei der FC-Kontroll-Prozedur spielt die Ankunftsreihenfolge der Pakete eine große Rolle. - Die FS-Kontroll-Prozedur arbeitet mit mehr Informationen als die FC-Prozedur. - Die FS-Prozedur kann mehr Pakete annehmen. - Bei der FS-Prozedur ist die Reihenfolge der Pakete uninteressant, da die Pakete in r sowieso sortiert werden. - Nachteil (aber nicht gravierend) bei den Kontroll-Prozeduren ist, daß b und k feste Werte sind. weiter mit ⌐ISO-Referenz-Modell@BS___6¬ AHBAA #!!# ISO-Referenz-Modell Insbesondere wenn es sich bei dem ⌐Rechnernetz@BS___6¬ um ein ⌐offenes System@BS___2¬ handelt, in das prinzipiell beliebige Rechner und DV-Endgeräte einbezogen werden können, muß bei der Datenübertragung dafür gesorgt werden, daß die Empfängerstation bereit und in der Lage ist, die zu übertragenden Daten anzunehmen und zu interpretieren. Ein zusätzliches Problem ergibt sich dadurch, daß die verwendeten Sende- und Empfangsgeräte von unterschied- lichen Hard- und Softwareherstellern kommen können. Innerhalb der @HPInternationalen Standard Organisation@HB (ISO, erarbeitet internationale technische Normen) hat man die Bedeutung von Standard- definitionen für die Nachrichtenübermittlung in Rechnernetzen erkannt. Mit ihrer Hilfe können Hersteller von Hard- und Software ihre Produkte aufein- ander abstimmen. Bei der Entwicklung des @HPISO-Referenz-Modells@HB ging man von der Idee eines offenen Systems aus. Man wollte ein Modell schaffen, das, aufbauend auf öffentlichen Datennetzen, die Kommunikation zwischen beliebigen Rechnern und Terminals ermöglicht. @HBDie Einrichtung von öffentlichen Packetvermittlungsnetzen stellt die Basis für die Realisierung von offenen Systemen dar. Das Architekturmodell für offene Systeme von ISO sollte die gesamte Hierarchie von der Kommunikation zwischen Benutzerprozessen bis hinunter zur Datenübertragung auf Leitungen umfassen. Das diesen Überlegungen zu Grunde liegende @HPSchichtenmodell@HB läßt sich folgendermaßen charakterisieren: In der obersten Schicht, der @HPAnwendungsschicht@HB (application layer), treten zwei Prozesse in Kommunikation. Sie bedienen sich dabei des darunter liegenden Kommunikationssystems, das durch weitere Schichten, von denen jede ganz bestimmte Aufgaben zu erfüllen hat, bis hinunter zum physischen Übertragungsmedium hierarchisch aufgebaut ist. Die Beziehungen zwischen Prozessen der gleichen Schicht werden (Schichten-) @HPProtokolle@HB genannt. @HBDurch den hierarchischen Aufbau und die klare Trennung der Schichten voneinander wird eine @HPModularisierung@HB erreicht. Dadurch werden für die Schicht n verschiedenartige Realisierungen ermöglicht, ohne daß die Schicht (n + 1) davon betroffen wäre, solange nur die Schnittstellen zwischen den Schichten identisch bleiben. Mit Ausnahme der untersten Schicht bedient sich jede Schicht n der Dienste der Schicht (n - 1), führt eigene Aufgaben durch und bietet der Schicht (n + 1) wiederum Dienste an. Die Beziehungen zwischen den benachbarten Schichten sind durch @HPDienstprotokolle@HB geregelt. Hauptkriterium für die konkrete Bildung von Schichten im Architekturmodell ist es, eng zusammengehörige Funktionen in einer Schicht zusammenzufassen und Funktionen, die nicht unmittlebar voneinander abhängen, in getrennte Schichten zu legen. @HBDie genannten Kriterien führten zur ersten Unterteilung in - Transportsystem und - Anwendersystem. Das ⌐ISO-Transportsystem@BS___6¬ dient, wie der Name schon sagt, dazu, Nachrichten von einem Ort an einen anderen, von einem Rechner oder Terminal zu einem anderen Endgerät, zu transportieren. Die Daten selbst werden dabei nicht beachtet und deren Verarbeitung nicht beeinflußt. Das ⌐ISO-Anwendersystem@BS___6¬ wiederum setzt den erfolgreichen Transport der Daten voraus. Es behandelt ausschließlich die Kommunikation zwischen Prozessen, deren Datenstrukturen und die Verarbeitung der Daten durch die Prozesse. Das Übertragungsmedium, über das die Prozesse kommunizieren, ist für das Anwendersystem uninteressant. Innerhalb dieser beiden Systeme werden noch weitere Abstufungen vorgenom- men, so daß das ISO-Modell aus 7 Ebenen besteht, 4 im Transportsystem und 3 im Anwendersystem. (Siehe folgende Graphik.) @HEDas ISO-Referenz-Modell @HA Schichten Endgerät Endgerät Layer @HB7. Anwendungs @HE▒▒▒▒@HO------Anwendungsprotokoll------@HE▒▒▒▒ @HBApplication @HB6. Darstellungs @HE▓▓▓▓@HO-----Darstellungsrotokoll------@HE▓▓▓▓ @HBPresentation @HB5. Sitzungs @HE▒▒▒▒@HO---------Sessionprotokoll------@HE▒▒▒▒ @HBSession @HB4. Transport @HE▓▓▓▓@HO-------Transportprotokoll------@HE▓▓▓▓ @HBTransport @HB3. Netzwerk @HE▒▒▒▒@HO----X.25----@HE≡≡≡≡@HO--Netzwerkpr.--@HE▒▒▒▒ @HBNetwork @HB2. Leitungs @HE▓▓▓▓@HO----HDLC----@HE≡≡≡≡@HO--Leitungspr.--@HE▓▓▓▓ @HBLink @HB1. physikalische @HE▒▒▒▒@HO-X.20--X.21-@HE≡≡≡≡@HO--physik. Pr.--@HE▒▒▒▒ @HBPhysical @HP▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ @HP▀▀▀▀ @HB: physikalisches Medium @HE≡≡≡≡ @HB: Vermittlungsrechner @HOHDLC @HB: High Level Data Link Control @HOX.25 @HB: CCITT-Empfehlung über die Zugriffsrechte zwischen DV-Endgerät und Datenübertragungseinrichtung (DÜE) @HOX.20, X.21 @HB: CCITT-Empfehlungen über die Schnittstelle zwischen DÜE und digitalem Netzwerk @HBweiter mit ⌐ISO-Transportsystem@BS___6¬ AHBAA #!!# ISO-Transportsystem Das Transportsystem des ⌐ISO-Referenz-Modell@BS___6¬s setzt sich aus 4 Schichten zusammen: 1. physikalische Schicht 2. Leitungsschicht 3. Netzwerkschicht 4. Transportschicht @HE1. Physikalische Schicht (physikal layer) @HB In der physikalischen Schicht werden die erforderlichen Eigenschaften des physikalischen Übertragungsmediums (elektrische Leitung, Richtfunk, optische Leitung, Telefonleitung, usw.) definiert. Dazu gehören die Darstellungsweise der einzelnen Signale, die Schnitt- stellen und die Topologie. @HE2. Leitungsschicht (link layer) @HB Die Leitungsschicht sorgt für den zuverlässigen Datenaustausch zwischen zwei Geräten, die durch das Übertragungsmedium der physikalischen Schicht miteinander verbunden sind. Die Übertragung von Nachrichten zwischen zwei Netzknoten in der Leitungs- schicht wird durch Protokolle gesteuert. @HBDie Aufgaben der Leitungsschicht sind: - @HPAuf- und Abbau von logischen Verbindungen@HB zwischen zwei Geräten. Dazu gehört auch das Initialisieren von Zählern für die Flußsteuerung, das Bereitstellen von Puffern zur Zwischenspeicherung von Paketen, das Setzen von Uhren für Time-Outs und ähnliches. - @HPFolgeprüfung: @HBDie richtige Reihenfolge von Paketen muß überprüft und garantiert werden. - @HPFlußsteuerung: @HBDie Überlastung des Netzes und von Teilverbindungen muß verhindert werden. - @HPFehlererkennung: @HBÜbertragungsfehler müssen erkannt werden. @HE3. Netzwerkschicht (network layer) @HB In dieser Schicht wird das gesamte Netzwerk betrachtet. Die Netzwerk- Schicht beschäftigt sich in erster Linie mit den Funktionen in den Netz- knoten und nicht mehr mit der eigentlichen Datenübertragung (diese wird von der Leitungsschicht geregelt). Die wesentlichen Funktionen der Netzwerkschicht sind: - Die ⌐Wegewahl@BS___6¬ (routing) - Festlegung der Multiplex-Strategie, also ob a) circuit-switching, b) message-switching oder c) packet-switching verwendet wird. (Dazu siehe ⌐Nachrichtenwege@BS___6¬.) @HE4. Transportschicht (transport layer) @HB In der Transportschicht ist die Struktur des gesamten Netzwerkes unsichtbar. Sichtbar für den Benutzer ist nur das Gegenüberstehen der beiden Wirtrechner. Die Funktionen der Transportschicht sind: - @HPAuf- und Abbau von End-zu-End-Verbindungen@HB End-zu-End-Verbindungen arbeiten nach dem "store and forward" Prinzip, wobei die Verbindungen nicht physisch durch Leitungs- schaltungen erstellt werden, sondern nur logisch durch Zuordnung in den Vermittlungsrechnern bzw. Vermittlungsknoten. - @HPAdreßzuordnung@HB - @HPZerlegung von Nachrichten@HB in Pakete und deren Zusammensetzung im Zielknoten, falls notwendig (abhängig von Nachrichtenlänge und Paketgröße) @HBweiter mit ⌐ISO-Anwendersystem@BS___6¬ AHBAA #!!# ISO-Anwendersystem @HBIm Anwendersystem werden 3 Schichten unterschieden, die innerhalb des ⌐ISO-Referenz-Modell@BS___6¬s die Schichten 5 - 7 umfassen: 5. Sitzungsschicht 6. Darstellungsschicht 7. Anwendungsschicht @HE5. Sitzungsschicht (session layer) @HB Eine @HPSession@HB ist eine Verbindung (Beziehung, Sitzung, Gespräch) zwischen zwei Prozessen zum Zweck der Kommunikation. Die Aufgabe der Session- Schicht ist es, solche Verbindungen zu unterstützen. Um zwei Benutzerprozesse in Verbindung treten zu lassen, werden zwischen ihnen Sessions errichtet. Nach ihrer Errichtung werden die Sessions dazu benutzt, den Datenaustausch zwischen den Benutzerprozessen zu steuern. Dazu gehört auch die Synchronisation der beiden Prozesse. Ein typisches Beispiel ist die login-Prozedur am Terminal. @HE6. Darstellungsschicht (presentation layer) @HB Während die Session-Schicht sich mit der Verwaltung von Sessions beschäf- tigt und dabei auf den Inhalt der Zwischen den Prozessen auszutauschenden Daten nicht eingeht, werden in der Darstellungsschicht gerade diese Daten näher betrachtet. Zweck dieser Ebene ist es, der Anwendungsebene die @HPInterpretation@HB der Daten zu ermöglichen. In homogenen Systemen bestehen in dieser Hinsicht nur geringe Schwierigkeiten. In heterogenen Systemen, das sind Systeme mit Rechnern (und Software) unterschiedlicher Hersteller oder Bauart, arbeiten kommunizierende Prozesse womöglich unter sehr verschiedenen Voraussetzungen. Die verwendeten Datenformate, Steuersprachen und Filestrukturen können dabei so unterschiedlich sein, daß sie ohne vorherige @HPTransformation@HB nicht interpretierbar wären. Als Beispiel sei hier die Umwandlung von Zeichen aus dem ASCII in den EBCDIC-Code bzw. umgekehrt genannt. @HBIn heterogenen Systemen besteht die Hauptaufgabe der Darstellungs- schicht also in der Transformation von Daten und darin, sie an die entsprechenden speziellen Gegebenheiten des Empfangsprozesses anzupassen. @HE7. Anwendungsschicht (application layer) @HB Auf dieser höchsten Ebene führen die Anwendungsprozesse die Anwendungen der Benutzer aus. Die Art und Weise, in der Prozesse hier kommunizieren, ist völlig anwendungsspezifisch. Es kann daher in dieser Schicht keine sinnvollen allgemeingültigen Standards geben. Dennoch können zwei Gruppen von Anwendungsprotokollen unterschieden werden: - Verwaltungs- und Systemprotokolle - Benutzergruppen spezifische Protokolle @HBIn die erste Gruppe fällt - die Verwaltung des gesamten verteilten Systems, - die Koordinierung der parallelen Prozesse, - Schutz vor unerlaubtem Zugriff, - Überwachung der Betriebsmittelvergabe und - das Vermeiden von Deadlocks. Konkret werden die meisten dieser Aufgaben vom Betriebssystem wahrgenom- men. Diese Systemprozesse treten mit Hilfe der darunterliegenden Ebenen miteinander in Kommunikation. Innerhalb bestimmter Benutzergruppen ist es oft sinnvoll, Anwendungsproto- kolle zu standardisieren (z. B. bei Datenbanken). @HBweiter mit ⌐Fremdnetze@BS___6¬ AHBAA #!!# Fremdnetze @HEAnschluß an Fremdnetze @HB Während die Transportschicht des ⌐ISO-Referenz-Modell@BS___6¬s davon ausgeht, daß Verbindungen auf allen Ebenen innerhalb eines wohldefinierten ⌐Netzwerk@BS___6¬es zustande kommen, ist es in der Praxis oft wünschenswert, auf mehrere Netzwerke, Zugriff zu haben, die an sich voneinander unabhängig sind. Basieren die betroffenen Netze auf der gleichen Topologie in der Hard- als auch in der Software (den Protokollen), so kann man sie einfach mittels einer Bridge koppeln. Eine @HPBridge@HB ist eine Hardware-Einrichtung, die mehrere Netze miteinander koppeln kann. Sind die Topologien völlig unterschiedlich, so muß man ein Gateway ver- wenden. Ein @HPGateway@HB ist in der Regel eine spezielle DV-Anlage zwischen zwei Knoten in verschiedenen Netzwerken. Seine wesentliche Auf- gabe besteht in der Protokoll-Umsetzung bzw. -Anpassung. @HB weiter mit Hintergrundspeicher (⌐HSV@BS___7¬)