Spicker PDF

Preview

Summary

Spicker...

Description

Fehlertoleranz: Ein System ist fehlertolerant, wenn es trotz Auftreten unvorhergesehener Fehler weiterhin in der Lage ist seine Funktion korrekt auszuführen. Systemsicherheit: Ein System gilt als sicher, wenn die Wahrscheinlichkeit auftretender Fehler minimiert ist. Fehlerarten: Permanente Fehler sind Fehler, die bei Auftreten die jeweilige Komponente oder das System permanent außer Betrieb setzen (z. B. defektes Laufwerk). Transiente Fehler sind solche Fehler, die dazu führen, dass eine Komponente oder ein System für ein bestimmtes Zeitintervall nicht korrekt arbeitet. Nach diese Zeitintervall ist der Fehler nicht mehr präsent und das korrekte Systemverhalten ist wiederhergestellt (z. B. temperaturabhängige Fehler). Sporadische Fehler sind generell immer präsent, zeigen sich allerdings nur in unregelmäßigen Intervallen als Fehlverhalten des Systems (z. B. Bitfehler in Datenübertragung). Fehler können in unkritische und kritische Fehler klassifiziert werden. Redundanz: Hardware- Redundanz: Funktionskritische Elemente eines Systems werden dupliziert (oder multipliziert), oder es wird eine spezielle Funktion auf unabhängige Komponenten verteilt. Dadurch wird gewährleistet, dass bei Auftreten eines Fehlers die Funktion weiterhin ausgeführt werden kann, obwohl es dabei zu einer Reduzierung der Qualität oder Effizienz kommen kann. Es kann unterteilt werden in statische und dynamische Redundanz. Während bei statischer Redundanz die redundanten Ressourcen aktiv sind, werden sie bei der dynamischen Redundanz bei Bedarf als Ersatzkomponenten aktiviert. Daher wird durch statische Redundanz also das Auftreten eines Fehlers maskiert und es ist nicht erkennbar, dass eine Systemkomponente ausgefallen ist (Hinreichende Fehlerbedingungen führen zum Ausfall des Gesamtsystems!) Bewertung der Fehlertoleranz

Fehlerrate: Die zu erwartende Anzahl von auftretenden Systemfehlern, also die Fehlerrate λ, wird wie folgt berechnet: 1 𝜆 =# 𝑀𝑇𝑇𝐹 Reparaturrate: Die Anzahl der möglichen Reparaturen, die in einer Zeiteinheit durchgeführt werden können, wird durch die Reparaturrate μ beschrieben. Da jede Reparatur im Durchschnitt MTTR Zeiteinheiten benötigt, wird die Reparaturrate mit ) Hilfe der mittleren Ausfalldauer wie folgt berechnet: 𝜇 =# *++, mittlere Fehlerhäufigkeit: Die Häufigkeit, mit der Systemfehler auf- treten können, werden von den Größen MTTF und MTTR bestimmt. Bei genauerer Betrachtung der Fehlergrößen wird klar, dass die Zeit zwischen zwei Fehlern nicht kleiner als MTTF + MTTR sein kann, denn während der Reparaturzeit ist das System nicht funktionsfähig. Daher wird die mittlere Fehlerhäufigkeit ν wie folgt berechnet: 1 𝜈 =# 𝑀𝑇𝑇𝐹 + 𝑀𝑇𝑇𝑅 Mit diesen Definitionen lässt sich nun die Verfügbarkeit, bzw. die Unverfügbarkeit des *++,

Systems ausdrücken. Die stationäre Unverfügbarkeit U ist somit 𝑈 =# *++12*++, *++, berechnet werden. Mit MTBF = MTTF + MTTR + MTTR, U kann als 𝑈 =# *+31

Die Unverfügbarkeit ist somit das Verhältnis der durchschnittlichen Reparaturzeit und dem durchschnittlichen Zeitintervall indem kein Fehler auftritt. Damit lässt sich die (stationäre) Verfügbarkeit V direkt ausdrücken: V = 1- U Es lässt sich durch algebraische Umformung zeigen, dass: *++1 *++1 =# # Damit beschreibt die Verfügbarkeit das Verhältnis der 𝑉 = 1−𝑈 =# *+31 *++1 2*++, durchschnittlichen Zeit bis zum Auftreten eines Fehlers und dem durchschnittlichen Zeitintervall indem kein Fehler auftritt. Ausfallsicherheit: Ist ein (analytisches) vom System festgelegtes Leistungsmerkmal. Verfügbarkeit: Ist ein vom Benutzer wahrgenommenes Leistungsmerkmal. Hammingdistanz und Hammingcodie rung: Der Hammingabstand (HD) zwischen zwei Codeworten ist die Anzahl der Bitstellen, an denen sich zwei Codeworte unterscheiden. Hammingabstand (HD) eines gesamten Codes C mit Codeworten c0 ... cy ist: 𝐻𝐷# = #𝑚𝑖𝑛{ℎ𝑑(𝑐𝑖, 𝑐𝑗)}∀𝑐𝑖, 𝑐𝑗# ∈ #𝐶, 𝑖# ≠ #𝑗# Um k Fehler zu erkennen, muss der Hammingabstand des gesamten Codes k + 1 betragen, zur Korrektur von k Fehlern, muss er 2k +1 betragen. Zyklische Redundanzprüfung – CRC: CRC (engl. Cyclic Redundancy Check) ist eine Kodierungsmethode zur Berechnung einer Bitfolge, die es ermöglicht zu erkennen, ob bei der Datenübertragung ein Bitfehler aufgetreten ist. CRC verwendet Polynomialcodes, die Bitfolgen als Polynome mit dem Koeffizienten 0 und 1 behandeln. Somit kann die in der Arithmetik etablierte Polynomdivision auch auf Bitfolgen angewendet werden um eine Prüfsumme (oder Errorkontrollcode (EDC: Error Detecting Code)) zu berechnen, der dann bei der Datenübertragung dem jeweilige, zu übertragenden Datenblock (oder Datenpaket) angehängt wird.

!

Schwanz- oder Rest-Division wird analog zur Division von Binärzahlen durchgeführt, mit dem Unterschied, dass die Subtraktion Modulo 2 durchgeführt wird. Ein Divisor passt in den Dividend, falls der Dividend genauso viele Bits wie dieser Divisor besitzt. Zur Berechnung des EDCs, müssen Sender und Empfänger sich vorab auf das Generatorpolynom G(x) einigen. Dieses Polynom wird dann vom Sender dazu verwendet den EDC zu berechnen. G(x) kann generell frei gewählt werden, solange die folgenden Bedingungen erfüllt sind: • Sowohl hochwertige und niedrigwertige Stellen (high- and loworder bits) von G(x) müssen eine 1 aufweisen • Um die Prüfsumme für einen Rahmen mit m Bits zu berechnen, die dem Polynom M(x) entspricht, muss es länger als G(x) sein Die Kernidee besteht darin, die Prüfsumme am Ende des Rahmens derart anzuhängen, dass das dadurch entstandene Polynom durch G(x) teilbar ist. Sei r der Grad von G(x). Man hänge r Nullstellen an M(x) an, was zu einer Länge von (m+r) Bits führt. Dies entspricht xrM(x). Man teile das Polynom, das durch die Bitsequenz xrM(x) dargestellt wird, durch die Nutzung von Polynomialarithmetik durch G(x). Man ziehe den Rest (≤ r Bits) von xrM(x) durch die Nutzung von Modulo- 2-Substraktion ab. Die dadurch entstandene Bitsequenz T(x) ist der Rahmen mit Prüfsumme, der übertragen wird. Übertragen wird das Polynom T(x), empfangen das Polynom T(x) + E(x); Sei E(x) das Errorpolynom, dann folgt aus E(x)=0, dass keine Fehler aufgetreten sind. Der Empfänger teilt T(x) durch G(x). Der dadurch entstandene Rest wird in zwei Fällen Null: E(x) war Null (d.h. es ist kein Fehler aufgetreten), oder E(x) ist genau durch G(x)

!

!

teilbar (was fälschlicherweise signalisiert, dass kein Fehler aufgetreten ist!). Man wähle G(x) so, dass der zweite Fall sehr unwahrscheinlich wird. Es muss sichergestellt werden, dass das Fehlerpolynom E(x) nicht genau durch G(x) teilbar ist. Die Wahrscheinlichkeit, dass ein Bitfehler der Form G(x) auftritt ist vernachlässigbar klein. Mit standardisiertem G(x) können die folgenden Fehler erkannt werden: I J 1. Alle einfachen Bitfehler: solange die 𝑥 #und 𝑥 #Terme Koeffizienten ungleich Null haben. 2. Alle zweifachen Bitfehler: solange G(x) einen Faktor mit mindestens drei Termen hat. 3. Jede ungerade Anzahl von Fehlern: solange G(x) den Faktor (x+1) enthält. 4. Alle Burstfehler (d.h. Sequenzen von aufeinanderfolgenden Bitfehlern) für die die Länge des Datenburst weniger als k Bits beträgt. 5. Die meisten Burstfehler für Datenbursts mit mehr als k Bits können auch erkannt werden. RAID: Mit RAID (Redundant Array of Independent Disks) werden mehrere unabhängige Festplatten zusammen geschaltet um ein großes logisches Laufwerk zu bilden. Auf diesem Array werden nicht nur Daten gespeichert, es werden auch "RedundanzInformationen" hinzugefügt. Diese Redundanz-Informationen können die Daten selbst sein (Spiegeln) oder Parity-Daten, die aus mehreren Datenblöcken berechnet werden (RAID 3, 4, 5 oder 6). Das eigentliche Ziel von RAID ist es, die Verfügbarkeit aller Daten zu erhöhen. RAID verhindert Ausfallzeiten bei einem Festplattenausfall. Aber auch die Performance wird gesteigert. RAID-Level 0 „Stripping“: Raid 0 ist eigentlich kein richtiges Raid, die Redundanz fehlt. Die einzelnen physikalischen Festplatten werden im einfachsten Fall hintereinander gehängt. So wird aus der kleinen Platte eine riesige logische Festplatte. Sollte aber eine physikalische Platte ausfallen, so sind alle Daten verloren, da die Informationen nicht redundant gespeichert wurden. Meist werden die Daten jedoch in Blöcke getrennt und dann auf den Platten verteilt. Es entsteht ein "Striping" der Daten. Dies erhöht die Performance der Zugriffe, da von vielen Festplatten quasi gleichzeitig gelesen bzw. auf sie geschrieben werden kann. RAID-Level 1 „Drive Mirroring“: Bei Raid 1 werden die Daten einfach noch einmal auf eine zweite physikalische Platte geschrieben. Dies ist der so genannte Spiegel. Fällt jetzt eine der beiden Festplatten aus, so sind die Daten immer noch auf der zweiten vollständig erhalten. Der Benutzung der logischen Platte kann normal weitergehen. Der große Nachteil sind die hohen Kosten, da für einen Nettobedarf von 72 GB zwei 72 GB Festplatten angeschafft werden müssen. RAID-Level 2 „Hamming System“: Die Daten werden in einzelne Bytes aufgeteilt und ein ECC (Error Correction Code) nach Hamming errechnet und auf dedizierte Festplatten geschrieben. Da heute alle Festplatten interne ECC-Berechnungen durchführen, wird diese Methode zur Korrektur einzelner Bit-Fehler nicht mehr verwendet. RAID-Level 3 „Byte-Striping mit dezidiertem Parity-Laufwerk“: Die Daten werden in einzelnen Bytes aufgeteilt und auf die Festplatten geschrieben. Die Parity-Informationen werden zu jeder Datenreihe auf die dedizierte Parity-Platte geschrieben. Dieser RAID-Level wird nur selten angewendet, da die Parity-Platte der Flaschenhals (bottle neck) ist. RAID-Level 4 „Block-Striping mit dezidiertem Parity-Laufwerk“: Dieses Verfahren ist mit dem RAID-Level 3 vergleichbar, jedoch werden die Daten in Blöcke aufgeteilt. Ein großer Nachteil sind Schreiboperationen, da die ParityInformationen berechnet und auf die eine dedizierte Festplatte geschrieben werden müssen. Diese Platte wird schnell zum Flaschenhals im Gesamtsystem. Der Flaschenhals kann dadurch verhindert werden, dass die Parity-Informationen im RAID-Controller zwischengespeichert und in großen Blöcken auf die Platte geschrieben werden. Der größte Vorteil von RAID 4 ist die Erweiterbarkeit um zusätzliche Festplatten ohne Umorganisation der Festplatteninhalte. Es wird eine Festplatte hinzugefügt, die Parity-Informationen bleiben erst einmal alle gleich, die Platte kann sofort genutzt werden. RAID-Level 5 „Block-Striping mit verteilter Parity“: Bei diesem Raid-Level werden die Daten nicht gespiegelt, sondern es wird eine Kontrollsumme berechnet, die auf eine der vorhandenen Festplatten geschrieben wird. n-1 Festplatten enthalten also die Nutzdaten, die Kontrollinformationen (Parity) wird auf die n-te Festplatte geschrieben, allerdings nicht immer auf die gleiche. Erst wird die erste, dann die zweite, die dritte und so weiter für die Parity-Informationen genutzt. Die anderen halten jeweils die Daten. Fällt eine Festplatte aus, so werden immer die fehlenden Informationen aus der Kontrollsumme errechnet. Dieser RAID-Level wird häufig bei Fileservern eingesetzt, für Datenbanken ist er wegen den etwas langsameren Schreibzugriffen nicht so gut geeignet. Zwei-Armeen-Problem: - Zwei Bataillone A-1 und A- 2 einer Armee A, die eine feindliche Armee B einkesseln - Angriff kann nur gewonnen werden, wenn die beiden Bataillone ihren Angriff synchronisieren und zur gleichen Zeit ausführen - Das jeweilige Bataillon der Armeen A wird nur angreifen, wenn es sich sicher ist, dass das andere Bataillon auch zur gleichen Zeit angreift - Der Bote der Nachricht muss durch das Gebiet von B - Für dieses Problem existiert keine Lösung! Um zu verstehen warum keine Lösung für dieses Problem existiert, muss man genauer untersuchen, was einen koordinierten Angriff verhindert. Man betrachte den Status von A-1 und A-2 zum Zeitpunkt t0, wenn noch keine Koordinationsbefehle per Bote gesendet wurden. Beide Bataillone haben keinerlei Informationen darüber wann die jeweilige andere Seite einen Angriff plant. Man nehme an, dass A-1 zum Zeitpunkt t1 eine Nachricht M der Form zu A-2 sendet. (Der Fall für A- 2 als Initiator ist symmetrisch). Eine Falluntersuchung zeigt, dass keines der beiden Bataillone sicher sein kann, dass das andere Bataillon die Nachricht erhalten hat. Man kann die folgenden Fälle unterscheiden: 1. Der von A-1 gesendete Bote und somit M1 erreichen A-2: In diesem Fall weiß zwar A2 das A- 1 plant am Samstag um 5:30 anzugreifen, A-1 kann allerdings nicht sicher sein, dass M1 von A-2 erfolgreich empfangen wurde. A-2 ist sich dessen bewusst und wird daher nicht angreifen. (Denn ein Angriff wir d nur stattfinden, wenn beide Bataillone sich sicher sind, dass das jeweilige andere Bataillon auch angreift). 2. Der von A-1 gesandte Bote wird von B gefangen genommen - somit erreichen Bote und M1 niemals A-2: A- 1 kann diesen Fall nicht vom ersten Fall unter- scheiden und wird somit nicht angreifen. 3. Der von A-1 gesandte Bote und somit M erreichen A- 2 später als die in M1 geplante Angriffszeit: In diesem Fall wird A-2 niemals angreifen, da die Koordinationszeit vergangen ist. A-1 kann diesen Fall nicht von den ersten beiden Fällen unterscheiden und wird nicht angreifen. Da A-1 nur angreifen darf, wenn es sicher ist, dass A- 2 zur gleichen Zeit angreift, muss im Fall 1 A-2 eine Empfangsbestätigung M2 der Form per Bote zu A-1 senden. Da M2 den gleichen Bedingungen wie M1 unterliegt, ist es möglich, dass M2 niemals von A-1 empfangen wird. Daher kann A-1 nicht zwischen den Fällen 1, 2 und 3 unterscheiden und darf somit nicht angreifen. Für A-2 ist die Situation ähnlich, da es niemals sicher sein kann, dass die Bestätigung M2 erfolgreich empfangen wurde. Es

ist somit für die Armee A unmöglich einen Angriff zu koordinieren, d.h. es existiert kein Protokoll, das zu einer fehlertoleranten Kommunikation führt. Stop- and- Wait- Protokoll: Verschiedene Übertragungssysteme verwenden unterschiedliche Signalkodierungen. Physikalische Spezifikationen, Anwendungsumgebung, Leistungskriterien und Kosten/Komplexität bestimmen die Protokollelemente in den ersten beiden Schichten. Ein Beispiel eines Protokollelementes der zweiten Schicht, was die fehlertolerante Datenübertragung realisieren soll, ist das bekannte Stop- and- Wait Protokoll. Im Folgenden werden die Komplexität st und die Details dieses Protokolls genauer untersucht. Dabei setzen wir voraus, dass Daten, die in den oberen Protokollschichten generiert wurden, an die zweite Schicht übergeben werden und in kleineren Übertragungseinheiten oder Frames übertragen werden. Das Ziel des Stop- and- Wait Protokolls ist den Sender und den Empfänger so zu koordinieren, dass der Sender nur einen neuen Frame sendet, wenn garantiert ist, dass der vorherige Frame korrekt empfangen wurde, um somit eine fehlertolerante Datenübertragung zu realisieren. Dieses Problem ist auf den ersten Blick dem 2 Armeen Problem sehr ähnlich, verlangt jedoch nicht die genaue Synchronisation von Sender und Empfänger. Eine naive Implementierung dieses Protokolls basiert auf der Bestätigung eines fehlerfrei empfangenen Frames, indem ein Acknowledgement!(ACK)!vom Empfänger zum Sender übertragen wird. Stellt der Empfänger fest, dass während der Übertragung (oder dem Empfang) ein Bitfehler aufgetreten ist, so wird eine negative Bestätigung (NACK) zum Sender übertragen. Da in den meisten Übertragungssystemen nicht garantiert werden kann, dass keine Fehler auftreten und dass die gesendeten Daten ihr Ziel erreichen, muss der Sender einen Timer aktivieren, der bei Ablauf eine Wiederholung des Sendevorgangs initiiert. Auf den ersten Blick scheint dieser Ansatz das gewünschte Resultat einer fehlertoleranten Kommunikation zu garantieren, bei genauer Untersuchung wird man allerdings feststellen, dass bei Miteinbeziehung von variablen Übertragungszeiten unerwünschte Nebenerscheinungen auftreten können. Man betrachte die Situation in der eine Empfangsbestätigung einer längeren Übertragungszeit unterliegt (Abb. Verzögerung in der Übertragung des ACK) und erst nach dem Ablauf des Timers beim Sender eintrifft. In diesem Fall muss der Sender den letzten Frame wiederholen, der dann beim Empfänger eintrifft. Der Empfänger hat allerdings keine Möglichkeit den ersten empfangenen Frame von dem wiederholten Frame zu unterscheiden und leitet beide zu den nächst höheren Schichten des Protokolls weiter. Somit wurden Teile des zu übertragenden Datenblocks dupliziert und der Empfänger hat fehlerhafte Daten an die Anwendung oder den Benutzer weitergeleitet. Das Protokoll kann dieses Problem verhindern, indem jeder Datenübertragungseinheit eine Identifikation in der Form einer Sequenznummer zugewiesen wird. Somit kann der Empfänger die duplizierten Daten von Neuübertragungen unterscheiden. Dieser Ansatz verhindert jedoch nicht den Effekt, der auftreten kann, wenn Empfangsbestätigungen während der Übertragung zerstört werden oder verloren gehen. Der Sender kann die ACKs und NACKs nicht eindeutig den gesendeten Frames zuordnen und das Ziel, eine fehlertolerante Datenübertragung zu realisieren, ist somit nicht erreicht. Dies ist in Abbildung (Verlust oder Zerstörung des ACK/NACK während der Übertragung) dargestellt. Es ist jedoch recht einfach dieses Problem zu beheben, indem jedem ACK/NACK eine Sequenznummer zugewiesen wird, die es eindeutig einem bestimmten Frame zuordnet. Die jeweiligen Schritte, die das Stop-and-Wait Protokoll auf der Senderseite (A) und Empfangsseite (B) implementieren, können wie in der untenstehenden Abbildung zusammengefasst werden. Fehlertoleranz durch Routing, OSI-Schicht 3: Das Routing stellt sicher, dass ein Kommunik ationspfad zwischen zwei Kommunikationspartnern gefunden wird. Dabei muss berücksichtigt werden, dass die jeweiligen Kommunikationspartner nicht direkt miteinander durch ein und dasselbe Kommunikationsmedium verbunden sind, sondern miteinander mittels mehrerer Netzwerkknoten kommunizieren. Die sogenannten Routingalgorithmen haben die Aufgabe, den besten Pfad in einem Kommunikationsnetz zu errechnen, wobei der beste Pfad ein kürzester Weg, basierend auf der Anzahl der notwendigen Übertragungsschritte, oder ein Pfad mit minimaler Latenzzeit ist. Man teilt die Routingalgorithmen grob in zwei Klassen ein: 1. Globale Routingalgorithmen (Link State Routing) Diese Algorithmen berechnen den kürzesten Pfad zu allen Knoten im Netz. Jeder der Knoten führt diesen Algorithmus unabhängig von den anderen Knoten aus. Die Eingabedaten bestehen aus der Gesamttopologie des Netzwerks mit allen Kommunikationsverbindungen und deren jeweiligen Kosten oder Latenz. Somit hat diese Routingmethodik zwei Phasen – das Erfassen der Netzwerktopologie und die Berechnung der besten Kommunikationspfade. Da sich die Bedingungen in einem Kommunikationsnetz ständig ändern können, müssen die topologischen Daten fortlaufend erfasst werden. Der eigentliche Routingalgorithmus ist ein zentralisierter Algorithmus, der für das sogenannte Link State Routing auf Dijkstras Kürzester Wege Algorithmus basiert. 2. Dezentralisierte (Verteilte) Routingalgorit hmen (Redundanz beimRouting) Dezentralisierte oder verteilte Routingalgorithmen haben die Eigenschaft, dass sie nicht erfordern die gesamte Topologie des Netzes lokal in einem Knoten zu aggregieren, um den besten Pfad zu ermitteln. Einer dieser Algorithmen ist der Distance Vector Algorithmus. Das Ziel dieses Algorithmus ist es, den besten Weg von einem Startknoten zu einem Endknoten zu ermitteln und somit ein fehlertolerantes Netzwerk zu realisieren. Das bedeutet, ein Netzwerkfehler in der Form einer ununterbrochenen Verbindung zweier benachbarter Knoten, oder der Ausfall eines Knotens selbst, muss nicht unbedingt zu einem Ausfall der Kommunikation zweier Knoten führen, wenn alternative Pfade verfügbar sind. Es gilt diese redundanten Pfade dynamisch zu ermitteln und den Datenverkehr von dem ausgefallenen Pfaden auf die Alternativwege umzuleiten. Dabei tauschen benachbarte Knoten asynchron und völlig unkoordiniert Informationen über die Erreichbarkeit anderer Knoten aus, auf denen die Erstellung einer Distanztabelle basiert. Was muss TCP tun, da es keine Aussage über die Kommunikationszeit der darunter liegenden Schichten treffen kann? Im Gegensatz zu den Protokollen der zweiten Schicht, die einen fehlerfreien Datenaustausch zwischen zwei direkt verbundenen Kommunik ationsknoten realisieren, muss die vierte Schicht Protokolle zur fehlerfre...